백준 2630번 색종이 만들기

백준 2630번 색종이 만들기 문제이다. 

 

문제는 다음과 같다. 

 

이번 문제는 분할 정복 문제로 분류되어 있다. 

분할 정복은 문제를 부분으로 나누어 푼것을 나중에 다시 합치는 것으로 재귀를 이용하여 풀어야 한다.

이번 문제를 보면 길이가 2의 배수로 진행된다. 

주어진 모양을 문제에 있는 것 처럼 4등분을 해서 각각을 다시 살펴본다.

나누다 보면 1칸이 될 것이고 갯수에 더해주면 된다. 

만약 나누었는데 전부 0이거나, 전부 1이면 더이상 나누지 않고 갯수를 더해준다.

 

코드는 다음과 같다. 

import sys

n = int(sys.stdin.readline().strip())
cnt1 = 0
cnt2 = 0
arr = []


def nemo(n, arr):
    global cnt1, cnt2
    if n == 1:
        if arr[0] == 1:
            cnt2 += 1
        else:
            cnt1 += 1
        return
    elif 0 in arr and 1 in arr:
        arr1 =[]
        arr2 =[]
        arr3 =[]
        arr4 =[]
        for i in range(n//2):
            for j in range(n//2):
                arr1.append(arr[i + j * n])
                arr2.append(arr[i+n//2 + j * n])
                arr3.append(arr[n*n//2 + i + j * n])
                arr4.append(arr[n*n//2 + i + j * n + n//2])
        nemo(n // 2, arr1)
        nemo(n // 2, arr2)
        nemo(n // 2, arr3)
        nemo(n // 2, arr4)
    elif arr[0] == 1:
        cnt2 += 1
    else:
        cnt1 += 1


for i in range(n):
    tmp = sys.stdin.readline().strip().split()
    for j in range(n):
        arr.append(int(tmp[j]))
nemo(n, arr)

print(cnt1)
print(cnt2)

배열의 요소를 찾는 부분이 좀 헷갈릴 수 있다. 

값을 잘 넣어주고 재귀형식으로 잘 만들어주면 쉽게 풀린다.

 

성공!