[Python] 1780번 종이의 개수

문제

https://www.acmicpc.net/problem/1780

풀이과정

• 크기를 자르는 방법
  1) 종이가 모두 같은 수라면 그대로 사용한다.
  2) 첫 경우가 아니라면 종이를 같은 크기의 종이9개로 자르고, 각각의 잘린 종이에 대해 1을 반복
  

• 설명
  문제의 첫번째 조건이 이해가 되지 않았다. 자른다는 기준이 명확하지 않기 때문이다. 차근차근 생각을 정리하였다.

  예제를 보았을 때,

  

  맨 왼쪽과 두번째의 경우 한가지 종류이니 그대로 사용하고 세번째의 경우에는 첫번째 조건을 만족하지 않으니 두번째 조건 과정을 거쳐야한다.

  하지만 임의로 잘랐을 경우에는 같은 크기의 9개로 자를 수 없으니, 가장 작은 종이의 크기는 1칸 이고 두번째로 작은 종이의 크기는 3x3의 형태가 될 것 이다.
  

가장 아래의 형태의 경우 2번째 조건 과정을 거칠 수 있을 것이다.
즉, 3^n * 3^n 형태로 잘라야한다.

• 구현할 것
  1. 시작점과 크기가 필요하다.
  2. 일정한 크기로 자른다.
     2-1. 해당 종이가 모두 같은 수로 되어있는지 판별한다.
     맞다면 해당 숫자를 cnt +=1 해준다.
     2-2. 아니라면 같은 크기의 종이 9개로 자른다.
  3. 2번을 재귀적으로 수행한다.

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

N = int(input())
m = [list(map(int, input().split())) for _ in range(N)]

cnt = [0, 0, 0]

def check(x, y, n):  # 시작점, 크기
    global cnt
    pick = m[x][y]
    for i in range(x, x+n):
        for j in range(y, y+n):
            if pick != m[i][j]: # 종류가 다를때 
                new_n = n // 3  # 영역을 3/1분할
                for mi in range(0, 3):
                    for mj in range(0, 3):
                        check(x + mi*new_n, y + mj*new_n, new_n)
                return
    cnt[pick] += 1

check(0, 0, N)
for i in range(-1, 2):
    print(cnt[i])

재귀 문제가 코드를 구현하는 것이 가장 어려운 것 같다. 반복적인 작업을 통해서 왜 답이 그렇게 나올 수 있는지 이해가 부족한 것 같다.