[Python] 2630 - 색종이 만들기 (실버2)

1. 문제 설명

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

2630번: 색종이 만들기

 

---

2. 아이디어

아예 분할 탐색을 쓰라고 문제에 사진까지 첨부해가며 어필하고 있다.

N = 2^k (1 <= k <= 7)이므로 N의 범위는 최대 128이 된다.

한창 열심히 시간복잡도 구하는 연습하던 시절

분할 탐색을 사용하면 시간복잡도가 해봐야 O(\(n^{2}log_{2}n\))이므로 충분히 통과할 수 있다.

---

3. 코드

cnt_w = 0
cnt_b = 0

def split(row, col, n, paper):
    global cnt_w
    global cnt_b

    color = paper[row][col]
    for y in range(row, row + n):
        for x in range(col, col + n):
            if (color != paper[y][x]):
                split(row, col, n//2, paper)
                split(row + n//2, col, n//2, paper)
                split(row, col + n//2, n//2, paper)
                split(row + n//2, col + n//2, n//2, paper)
                return
    if color == 0:
        cnt_w += 1
    else:
        cnt_b += 1

def solution():
    n = int(input())
    paper = [list(map(int, input().split())) for _ in range(n)]

    split(0, 0, n, paper)
    print(cnt_w)
    print(cnt_b)

solution()