문제 링크

• https://www.acmicpc.net/problem/2630

문제 설명

• 한 변의 길이가 2**N인 정사각형이 있다

• 모두 0이거나 1이면 카운트

• 아니면 1/4로 잘라 반복

• 카운트 0, 카운트 1 각각 출력

풀이

• 재귀 함수 구현

• 현재 범위에 대해 체크

• 모두 1이거나 모두 2일 경우 카운트 후 종료

• 아니면 네 부분에 대해 재귀

코드

import sys


def init():
    ipt = sys.stdin.readline
    n = int(ipt())
    board = [list(map(int, ipt().split())) for _ in range(n)]
    return n, board, 0, 0


def check(start, end):
    global count0, count1
    sy, sx = start
    ey, ex = end
    all0, all1 = True, True
    for i in range(sy, ey+1):
        for j in range(sx, ex+1):
            if board[i][j]:
                all0 = False
            else:
                all1 = False
    if all0:
        count0 += 1
        return
    if all1:
        count1 += 1
        return
    my = (sy+ey) // 2
    mx = (sx+ex) // 2
    check((sy, sx), (my, mx))
    check((sy, mx+1), (my, ex))
    check((my+1, sx), (ey, mx))
    check((my+1, mx+1), (ey, ex))


sys.setrecursionlimit(10000)
n, board, count0, count1 = init()
check((0, 0), (n-1, n-1))
print(count0)
print(count1)