백준 1780 종이의 개수

https://www.acmicpc.net/problem/1780

1780번: 종이의 개수

종이에 써져있는 숫자가 모두 같다면 그걸 하나로 보고 아니면 9개로 자른다.

 

9개로 자른다는것은 사각형의 좌측상단. 즉 처음 시작점에 대한 좌표를 알아내면 된다.

 

각 좌표는 (x + i * n//3, y + j * n//3)라는 규칙을 가지고 있다.

 

처음에 0,0으로 시작해서 0,0이 -1, 0, 1인지 기준을 잡은다음에 n x n까지 돌리는데 

 

만약 1개라도 잘못 나오게 된다면 그 즉시 그 종이는 잘못된것이므로

 

9개로 나눠서 분할정복을 시작하고 원래 있던건 return을 통해 없애준다.

 

 

def divide_paper(x,y,n):
    std = paper[x][y]

    for i in range(x,x+n):
        for j in range(y,y+n):
            if paper[i][j] != std:
                for a in range(3):
                    for b in range(3):
                        divide_paper(x+a*n//3, y+b*n//3, n//3)
                return
    if std == -1:
        data[0] += 1
    elif std == 0:
        data[1] += 1
    else:
        data[2] += 1


n = int(input())

paper = []
data = [0,0,0]
for _ in range(n):
    paper.append(list(map(int,input().split())))

divide_paper(0,0,n)
for i in data:
    print(i)