[백준] 1780 종이의 개수, python

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

1780번: 종이의 개수

import sys
input = sys.stdin.readline
def devide(r, c, size):
    global m1, z, p1
    if check(r, c, size):
        if paper[r][c] == -1:
            m1 += 1
        elif paper[r][c] == 0:
            z += 1
        else:
            p1 += 1
        return
    # 분할
    for i in range(r, r + size, size//3):
        for j in range(c, c + size, size//3):
            devide(i, j, size//3)

def check(r, c, size):
    value = paper[r][c]
    for i in range(size):
        for j in range(size):
            if paper[r + i][c + j] != value:
                return False
    return True

if __name__ == "__main__":
    N = int(input())
    paper = [list(map(int, input().split())) for _ in range(N)]
    global m1, z, p1
    m1, z, p1 = 0, 0, 0
    devide(0, 0, N)
    print("{}\n{}\n{}".format(m1,z,p1))

 

분할 정복 문제로 Top Down 방식으로 풀었다. (Bottom Up 방식으로도 풀수 있는 문제긴 하다)

문제 설명에 나와있는대로 종이가 같은수로 되어있으면 그대로 사용하고 아닌경우에 종이에 같은 수만 있을때까지 아홉 등분한다.

재귀를 사용해서 기저 조건인지 파악하고 아닌경우 분할 하는 방식으로 진행하면 된다.

처음 구할땐 size == 1인 경우를 기저 조건으로 잡았는데 check 함수가 해당 경우까지 포함하고 있어서 제외하였다.

check 함수는 같은수가 되어있는지 확인하는 함수로 중간에 하나라도 다른 값이 있으면 False를 반환한다.

check함수에서 True를 반환받으면 종이에 값을 추가하는데 제일 첫값으로 저장할 변수를 지정한다.

False를 반환 받은경우 분할을 하게 되는데 이중 반복문을 사용해서 구현하였다.

---

이전에도 비슷한 문제가 있었는데 그땐 N 이 2의 지수로 되어있어서 조금더 간단한 문제였다.