[백준] 2630 색종이 만들기 python

www.acmicpc.net/problem/2630

2630번: 색종이 만들기

import sys; input = sys.stdin.readline
N = int(input())
color_paper = [list(map(int, input().split())) for _ in range(N)]
def check(color, r, c, size):
    for i in range(r, r + size, visit[r][c]):
        for j in range(c, c + size, visit[r][c]):
            if color_paper[i][j] != color:
                return False
            if visit[r][c] != visit[i][j]:
                return False
    visit[r][c] *= 2
    return True

# bottom up
white, blue = 0, 0
for r in color_paper:
    tmp = sum(r)
    blue += tmp
    white += N - tmp

cnt = 2
visit = [[1] * N for _ in range(N)] # 어떤 크기로 합쳐져있는지 확인하기 위한 값
while cnt <= N:
    # cnt 등분 되어있는 모든 색종이를 확인
    for i in range(0, N, cnt):
        for j in range(0, N, cnt):
            ret = check(color_paper[i][j], i, j, cnt)
            if ret: # 합칠수 있음, 작은색종이 4-> 큰색종이 1
                if color_paper[i][j]: # 파란색 
                    blue -= 3 
                else:
                    white -= 3
    # 한바퀴 다 돌면 cnt *= 2
    cnt <<= 1
print(white, blue, sep='\n')

분할정복을 사용해서 푸는 문제이다.

top down인 분할정복보다 bottom up 방식을 더 쉽게 구현할것 같았다.

초기값으로 size가 1인 흰종이와 파란종이의 개수를 저장하고 크기를 키워가면서 합칠수 있는경우 해당 색종이에서 -3씩 빼주었다.

합칠수 있는 경우는 색깔이 같아야하고, 색종이의 사이즈가 같아야한다.

색종이의 사이즈가 같은 것을 확인하기 위해서 visit이라는 이차원 배열을 만들어두고 갱신하였다.

visit도 초기값은 1이고 합쳐지면 visit[r][c] *= 2를 하여 사이즈를 갱신한다.

이때 사이즈 갱신하는 부분은 각 크기별 색종이의 (0,0) 부분이다.

모든 구간을 확인하면 흰 종이와 파란 종이의 총 갯수가 나오게 된다.