출처 : 2630번: 색종이 만들기
종이의 크기가 N x N인 정사각형에서 각 칸에 1(파란색)과 0(하얀색)으로 칠해져있을 때 일정한 규칙에 따라 잘라서 자른 모든 면이 모두 같은 색이면 그 칸의 수를 반환하고, 모두 같은 색이 아니라면 똑같은 크기의 N/2 x N/2색종이로 조건을 만족할 때 까지 반복한다.
import sys
N = int(sys.stdin.readline())
paper = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
result = []
def solution(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] :
solution(x, y, N//2)
solution(x, y+N//2, N//2)
solution(x+N//2, y, N//2)
solution(x+N//2, y+N//2, N//2)
return
if color == 0 :
result.append(0)
else :
result.append(1)
solution(0,0,N)
print(result.count(0))
print(result.count(1))
n
의 최대가 128이고, 2차원 배열이기때문에 (128 * 128) = 16384이고, 분할 정복의 TC는 O(NlogN)
이기 때문에 주어진 1초안에 충분히 가능하다.