알고리즘 - Python / 백준 - 1780번 : 종이의 개수

1780번: 종이의 개수 (acmicpc.net)

1780번: 종이의 개수

 

---

풀이

• 3의 제곱수로 이루어진 정사각형의 종이를 한 정사각형안에 같은 숫자로만 이루어지도록 하고 그렇지 않으면 9등분을 반복하는 문제이다.
• 따라서 더 잘라야할 상황이 나오면 더 자르도록 분할해서 해결하면 된다.
• 재귀함수를 통해서 문제 분할을 구현하였다.

 

import sys

stack = []
n = int(sys.stdin.readline())
for _ in range(n):
  stack.append(list(map(int, input().split())))

def check(start_x,start_y,n):
  global stack
  hold_check = 0
  hold = stack[start_y][start_x]
  for i in range(start_y,start_y+n):
    for t in range(start_x,start_x+n):
      if hold != stack[i][t]:
        hold_check = 1
        break
  if hold_check == 1:
    new_n = int(n/3)
    ans_1 = 0
    ans_2 = 0
    ans_3 = 0
    for i in range(start_y,start_y+n,new_n):
      for t in range(start_x,start_x+n,new_n):
        ans1 , ans2 , ans3 = check(t,i,new_n)
        ans_1 += ans1
        ans_2 += ans2
        ans_3 += ans3
    return (ans_1,ans_2,ans_3)
  elif hold_check == 0:
    if hold == -1:
      return (1,0,0)
    elif hold == 0:
      return (0,1,0)
    elif hold == 1:
      return (0,0,1)

ans1 , ans2, ans3 = check(0,0,n)
print(ans1)
print(ans2)
print(ans3)

---