[Baekjoon 2630 / python / 실버2] 색종이 만들기

import sys

n = int(sys.stdin.readline())  # 종이 길이

paper = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]  # 종이와 색깔

result = []   # 결과를 담을 변수

def cut(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]:  # 다른 색깔이 존재할 경우 종이를 4등분한다

                cut(x, y, n//2)

                cut(x+n//2, y, n//2)

                cut(x, y+n//2, n//2)

                cut(x+n//2, y+n//2, n//2)

                return  # 4등분한 하위 함수에서 이미 결과를 제출했을 것이므로 return 한다

    # 종이 색깔이 모두 같다면 result에 결과 담기

    if color == 0:

        result.append(0)

    else:

        result.append(1)

# 함수 실행

cut(0, 0, n)

# 결과 출력

print(result.count(0))

print(result.count(1))

 

분할 정복 문제이다. 분할 정복은 큰 문제를 작은 문제의 단위로 나누어 해결한 후 그것을 합쳐 큰 문제를 해결하는 방법을 말한다.

 

이 문제는 특이하게도 문제 설명에 문제의 해결방법을 제시해 주고 있다. 이 방법을 이해하고 그것을 코드로 작성하기만 하면 되는데... 방법은 이해했는데 코드로 작성하는게 너무나도 헷갈렸다.

 

방법을 알려주고 코드를 작성하는 것 마저 어렵기 때문에 실버2의 난이도를 가지고 있지 않나 싶다.

한번 문제를 풀고 나면 이게 왜 헷갈렸었는지 이해가 안 될 정도로 단순하다.