오늘의 문제 - boj-2630

문제

풀이

주어진 정사각형을 4분할 하려면 초기값 r, c에서 아래와 같이 n//2를 더해가면 그림에서 주어진 순서대로 시작인덱스를 구할 수 있다.
1. r, c
2. r, c + n//2
3. r +n//2, c
4. r+n//2, c+n//2

구한 시작인덱스를 토대로 길이값 n을 더해 끝 인덱스 값을 구해주고 순회하면서 색이 같은지 검사할 수 있다. 색을 구했다면 갯수를 저장하는 리스트 color_cnt에 각 값을 저장해준다.

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

color_cnts = [0] * 2
def is_whole_paper_equal(r,c,n):
    if n == 0:
        return
    cur_paper = papers[r][c]
    for i in range(r, r+n):
        for j in range(c, c+n):
            if papers[i][j] != cur_paper:
                return False
    return True

def get_cnt_of_color(r,c,n):
    if is_whole_paper_equal(r,c,n):
        color_cnts[papers[r][c]]+=1
    else:
        for partial_row in range(2):
            for partial_col in range(2):
                get_cnt_of_color(r + partial_row * n//2 , c + partial_col * n//2, n//2)

get_cnt_of_color(0, 0, N)

for color_cnt in color_cnts:
    print(color_cnt)