색종이 만들기

• 색종이로 설명을 하긴 했지만, 쿼드트리로 압축할때의 데이터의 크기를 계산하는 문제이다. 쿼드트리로 압축한 데이터 자체를 구하는 문제로는 쿼드트리 의 약화버전
• 특별한 알고리즘은 필요 없고 그냥 구현하면 된다. 재귀로 구현해도 되지만 여기에서는 그냥 바텀업으로 이터레이티브하게 구현했다. 어느쪽으로 구현하든 N*N + (N/2 * N/2) + (N/4 * N/4) + … (1 * 1) = (N^2)/3 = O(N^2) 의 시간이 걸린다.

"""Solution code for "BOJ 2630. 색종이 만들기".

- Problem link: https://www.acmicpc.net/problem/2630
- Solution link: http://www.teferi.net/ps/problems/boj/2630
"""

WHITE = '0'
BLUE = '1'


def main():
    N = int(input())
    colors = [input().split() for _ in range(N)]
    white_counts = []
    blue_counts = []
    for row in colors:
        white_counts.append([int(col == WHITE) for col in row])
        blue_counts.append([int(col == BLUE) for col in row])

    size = 1
    while size < N:
        delta = [(0, 0), (0, size), (size, 0), (size, size)]
        size *= 2
        for r in range(0, N, size):
            for c in range(0, N, size):
                white = sum(white_counts[r + dr][c + dc] for dr, dc in delta)
                blue = sum(blue_counts[r + dr][c + dc] for dr, dc in delta)
                if white == 4 and blue == 0:
                    white = 1
                elif white == 0 and blue == 4:
                    blue = 1
                white_counts[r][c], blue_counts[r][c] = white, blue

    print(white_counts[0][0])
    print(blue_counts[0][0])


if __name__ == '__main__':
    main()