[백준 #1780] 종이의 개수

1. 문제 설명

2. 해설

문제의 크기를 3개씩 잘라서 풀어내는 분할 정복 문제. 내 접근 방식은 이렇다.

1. 종이가 같은 수로 이루어져 있는지 검사한다.
2. 같은 수로 이루어지지 않았다면 3*3개로 종이를 자른다.
3. 모든 종이를 탐색할 때까지(종이의 크기가 1이 될 때까지) 1번, 2번을 반복한다.

처음에는 배열을 직접 자를까 생각했다가, index를 잘 조절하는게 시간 복잡도 측면에서 더 낫다고 생각했다. N은 3의 제곱수로만 나온다고 했으니, 인덱스 조절을 i*n//3으로 해주면 된다.

3. 코드

from sys import stdin
input = stdin.readline


# 종이가 모두 같은 수로 되어 있는지 검사
def check(sx, sy, n):
    tmp = paper[sx][sy]
    for i in range(n):
        for j in range(n):
            if paper[sx+i][sy+j] != tmp:
                return False

    return True


# 분할 정복
def divide_and_conquer(sx, sy, n):
    if check(sx, sy, n):
        res[paper[sx][sy] + 1] += 1
    else:
        for i in range(3):
            for j in range(3):
                divide_and_conquer(sx + i*n//3, sy + j*n//3, n//3)  # 종이를 9개씩 분할

    return


N = int(input())
paper = [list(map(int, input().split())) for _ in range(N)]
res = [0, 0, 0]

divide_and_conquer(0, 0, N)
for r in res:
    print(r)