[분할정복] 백준 1780: 종이의 개수

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


시작: 21.05.17 23:21
끝: 21.05.17 23:35
디버깅: 21.05.18 00:01
성공: 

[아이디어]
이거야말로... 9개로 분할해서 9번 재귀 도는 문제다!!


[시간복잡도]



[실수]


[검색]


[개선/추가사항]

"""



global paper_count
global arr

# -1, 0, 1 순서
paper_count : list = [0, 0, 0]

def solve(size: int, x: int, y: int) -> None:
    global paper_count
    global arr


    first_num: int = arr[x][y]

    # 기저
    if size == 1:
        paper_count[first_num] += 1
        return


    # 숫자가 다 같은지 확인
    all_same_num = True

    i: int = 0

    # 실수: i < size으로 해야 하는데 i < 3으로 함..
    while all_same_num and i < size:
        for j in range(size):
            # print(f"arr[{x+i}][{y+j}] = {arr[x+i][y+j]}")
            if (first_num != arr[x+i][y+j]):
                all_same_num = False
                # print("false")
                break
        i += 1

    if all_same_num:
        paper_count[first_num] += 1
        # print("숫자 같아서 리턴")
        return
    
    else:
        next_size = int(size/3)

        # print(f"size = {size}, nSize = {next_size}")

        # print(f"solve({next_size}, {x}, {y})")
        solve(next_size, x, y)
        # print(f"solve({next_size}, {x+ next_size}, {y})")
        solve(next_size, x + next_size, y)
        # print(f"solve({next_size}, {x+ next_size * 2}, {y})")
        solve(next_size, x + next_size * 2, y)


        # print(f"solve({next_size}, {x}, {y+ next_size})")
        solve(next_size, x, y + next_size)
        solve(next_size, x + next_size, y + next_size)
        solve(next_size, x + next_size * 2, y + next_size)

        solve(next_size, x, y + next_size * 2)
        solve(next_size, x + next_size, y + next_size * 2)
        solve(next_size, x + next_size * 2, y + next_size * 2)
    




import sys
input = sys.stdin.readline

N = int(input())

# 각 종이에 +1을 미리 하여 인덱스로 활용
arr = [list(map(lambda x: int(x) + 1, input().split())) for _ in range(N)]
# print(len(arr))


# 실수... solve(9, 0, 0)이라고 했다.
solve(N, 0, 0)

for answer in paper_count:
    print(answer)