2063 색종이 만들기 바로가기
접근방식
- 분할정복 방법을 사용하여 푸는 방법이다. 어떤 규칙으로 분할을 하고 합칠 것인지가 관건이다.
- 이 문제의 분할 규칙은
기준점(내 코드에서는 나뉘어진 배열의 0,0)과 다른 색이 나온다면 분할을 한다. 이다. - 모든 색깔이 다 같다면 그 색깔 변수에 + 1을 해준다.
파이썬 코드
import sys
n = int(sys.stdin.readline())
paper = []
w = 0
b = 0
for _ in range(n):
paper.append(list(map(int,sys.stdin.readline().split())))
def check(n,i,j):
global w,b
s = paper[i][j]
for ii in range(i, i + n):
for jj in range(j, j + n):
# 분할 지점 (Divide)
if paper[ii][jj] != s:
check(n // 2, i, j)
check(n // 2, i, j + (n // 2))
check(n // 2, i + (n // 2), j)
check(n // 2, i + (n // 2), j + (n // 2))
return
if s == 0:
w = w + 1
return
else:
b = b + 1
return
check(n,0,0)
print(w)
print(b)
