BOJ 분할정복 : 색종이 만들기 (2630)

www.acmicpc.net/problem/2630

문제정의

• 0은 흰색, 1은 파란색이다. 각 색깔 별로 몇개의 정사각형 색종이를 만들수 있는지 찾으시오.
• 예시에서는 9개의 흰색종이와 7개의 파란색종이를 만들 수 있다.

정답코드

• 재귀~

n = int(input())
paper = []
for i in range(n):
    paper.append(list(map(int, input().split(" "))))

n = 8
paper = [[1, 1, 0, 0, 0, 0, 1, 1], 
		[1, 1, 0, 0, 0, 0, 1, 1], 
        [0, 0, 0, 0, 1, 1, 0, 0], 
        [0, 0, 0, 0, 1, 1, 0, 0], 
        [1, 0, 0, 0, 1, 1, 1, 1], 
        [0, 1, 0, 0, 1, 1, 1, 1], 
        [0, 0, 1, 1, 1, 1, 1, 1], 
        [0, 0, 1, 1, 1, 1, 1, 1]]

result = []
def find_square(x, y, n):
    color = paper[x][y]
    for i in range(x, x+n):
        for j in range(y, y+n):
            if color != paper[i][j]:
                find_square(x, y, n//2) # 좌 상단 정사각형
                find_square(x, y+n//2, n//2) # 좌 하단 정사각형
                find_square(x+n//2, y, n//2) # 우 상단 정사각형
                find_square(x//2, y//2, n//2) # 우 하단 정사각형
                return
    # code gets here only when color == papercell(x,y) ~ papercell(x+n, y+n)
    if color == 0:
        result.append(0)
    if color == 1:
        result.append(1)

find_square(0,0,n)
print(result.count(0)) # 12개의 흰색종이
print(result.count(1)) # 7개의 파란색종이