백준 1780 종이의 개수 (파이썬)
접근방식
- 백준 2630 색종이 만들기 문제와 똑같은 방식으로 분할정복 방법을 사용하여 푸는 방법이다. 어떤 규칙으로 분할을 하고 합칠 것인지가 관건이다. 2630 색종이 만들기 문제는 아래 링크에서 확인할 수 있다.
https://ataraxiady.github.io/dev/2021/04/10/dev-boj-1_2630/
- 이 문제의 분할 규칙은 마찬가지로
기준점(내 코드에서는 나뉘어진 배열의 0,0)과 다른 숫자가 나온다면 9등분으로 분할을 한다.이다. - 4등분이 9등분이 된 것 뿐이므로 분할 부분을 수정해주면 된다.
파이썬 코드
import sys
n = int(sys.stdin.readline())
paper = []
zero = 0
positive_one = 0
negative_one = 0
for _ in range(n):
paper.append(list(map(int,sys.stdin.readline().split())))
def check(n,i,j):
global zero, positive_one, negative_one
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 // 3, i, j)
check(n // 3, i + (n // 3), j)
check(n // 3, i + 2 * (n // 3), j)
check(n // 3, i, j + (n // 3))
check(n // 3, i + (n // 3), j + (n // 3))
check(n // 3, i + 2 * (n // 3), j + (n // 3))
check(n // 3, i, j + 2 * (n // 3))
check(n // 3, i + (n // 3), j + 2 * (n // 3))
check(n // 3, i + 2 * (n // 3), j + 2 * (n // 3))
return
if s == 0:
zero += 1
return
elif s == 1:
positive_one += 1
return
else:
negative_one += 1
return
check(n,0,0)
print(negative_one)
print(zero)
print(positive_one)
