[백준] 1780번 - 종이의 개수 Python 파이썬

📄 문제

❗️풀이

분할정복을 이용하면 된다.
1. 영역 내 모든 숫자가 -1, 0, 1로 동일하다면 해당 숫자의 count를 세는 변수를 +1 해준다.
   - count 변수는 global 선언하여 함수를 빠져나온 뒤에도 값이 유지되게 설정했다.
   - -1, 1이 포함되어 있기 때문에 sum이 아닌 순회하면서 다른 숫자를 만나는지 여부로 확인했다.
2. 동일하지 않다면 영역을 9분면으로 쪼개서 각 영역에 대해서 -1, 0, 1로 동일한지 확인한다.
3. 2번의 작업은 재귀함수로 진행이 가능하다.

✏️ 코드

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

N = int(input())
paper = []
for _ in range(N):
    p = list(map(int, input().rstrip().split()))
    paper.append(p)

def divide_paper(n,row, col):
    global cnt
    first = paper[row][col]
    # 원소가 1개면
    if n == 1:
        cnt[first] += 1
        return 
    # 영역 내에 다른 수가 존재하는지 확인
    for i in range(row, row+n):
        for j in range(col, col+n):
        	# 처음 등장한 숫자와 다르다면 분할 시행
            if paper[i][j] != first:
                tri = n//3 
                for i in range(3):
                    for j in range(3):
                        divide_paper(tri, row+i*tri, col+j*tri)
                return
    # 없으면 하나의 종이로 판단
    cnt[first] += 1

cnt = [0]*3
divide_paper(N, 0, 0)

for num in range(-1,2):
    print(cnt[num])

스스로 풀이 완료!