[백준] 2630번, 색종이 만들기

 

 

 

 

 

 

 

접근법

- 분할 정복 기법 카테고리 문제를 골랐다. 분할 정복 기법을 사용하여야 된대서 어떤 식으로 풀어야 할지 고민을 하다가 다른 분들의 풀이법을 참고해가면서 풀었다.

 

- 생각보다는 특별한 기법없이 재귀를 사용하여 4 분할하는 방식으로 풀었다. 4 분할한 정사각형이 같은 색인지를 체크하고 같은 색이라면 해당 색에 +1, 다른 색이 하나라도 존재하면 그것을 다시 4 분할하는 방식으로 상당히 직관적인 풀이였다.

 

- white, blue 변수를 global로 선언해서 함수 내부에서 사용하게 하는 것만 주의하면 특별한 것은 없는 것 같다.

 

 

 

 

 

 

풀이

import sys

input = sys.stdin.readline
N = int(input())
paper = [list(map(int, input().split())) for _ in range(N)]
# N = 8
# paper = [[1, 1, 0, 0, 0, 0, 1, 1], [1, 1, 0, 0, 0, 0, 1, 1], [0, 0, 0, 0, 1, 1, 0, 0], [0, 0, 0, 0, 1, 1, 0, 0], [1, 0, 0, 0, 1, 1, 1, 1], [0, 1, 0, 0, 1, 1, 1, 1], [0, 0, 1, 1, 1, 1, 1, 1], [0, 0, 1, 1, 1, 1, 1, 1]]
# white, blue = 0, 0

def color_check(i, j, n) :
    for p in range(i, i + n) :
        for q in range(j, j + n) :
            if paper[p][q] != paper[i][j] :
                return False
    return True

def dnc(i, j, n) :
    global white, blue

    if color_check(i, j, n) :
        if paper[i][j] == 1 :
            blue += 1
        else :
            white += 1
        return
    else :
        dnc(i, j, n // 2)
        dnc(i + n // 2, j, n // 2)
        dnc(i, j + n // 2, n // 2)
        dnc(i + n // 2, j + n // 2, n // 2)
        return

dnc(0, 0, N)
print(white)
print(blue)

 

 

 

 

 

 

 

결과