Baekjoon Online Judge 1780번 파이썬. 분할 정복.

문제 링크
https://www.acmicpc.net/problem/1780

1780번: 종이의 개수

2630번 문제와 유사하다.
다른 점은 9개로 자르는 것이기 때문에 ‘N//3’을 하고, 재귀함수의 시작점. x,y가 9개 있다는 것이다.

정답 코드

N = int(input())
matrix = [list(map(int,input().split()))for i in range(N)]

result = []
def solution(x,y,N):
  number = matrix[x][y]
  for i in range(x,x+N):
    for j in range(y,y+N):
      if number != matrix[i][j]:
        n = N//3
        solution(x,y,n)
        solution(x,y+n,n)
        solution(x,y+2*n,n)
        solution(x+n,y,n)
        solution(x+n,y+n,n)
        solution(x+n,y+2*n,n)
        solution(x+2*n,y,n)
        solution(x+2*n,y+n,n)
        solution(x+2*n,y+2*n,n)
        return
  if number == -1:
    result.append(-1)
  elif number == 0:
    result.append(0)
  else:
    result.append(1)

solution(0,0,N)
print(result.count(-1))
print(result.count(0))
print(result.count(1))