[Python] BOJ/백준 1780번 종이의 개수

[문제]

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

1780번: 종이의 개수

 

[풀이]

2021.08.11 - [BOJ] - [Python] BOJ/백준 2630번 색종이 만들기

[Python] BOJ/백준 2630번 색종이 만들기

 

2630번 색종이 만들기와 유사한 문제!

다만 2630번은 4분할로 나누면 되지만 이번 문제는 9분할로 나눠야 하는 문제이다.

따라서 cut 함수를 9번 불러줘야하는데, x와 y의 시작점을 잘 계산하면 쉽게 풀 수 있는 문제이다.

 

그림 설명과 코드 주석에 써놓았듯이 차례대로

1번 영역의 경우 cut(x, y, n // 3) ,

9번 영역의 경우 cut(x + n // 3 * 2, y + n // 3 * 2, n // 3) 이다.

 

[코드]

import sys


def cut(x, y, n):
    global minus, zero, plus
    num = paper[x][y]   # 첫 번째 숫자

    for i in range(x, x+n):
        for j in range(y, y+n):
            if num != paper[i][j]:
                # 1, 2, 3
                cut(x, y, n // 3)
                cut(x, y + n // 3, n // 3)
                cut(x, y + n // 3 * 2, n // 3)
                cut(x + n // 3, y, n // 3)
                # 4, 5, 6
                cut(x + n // 3, y + n // 3, n // 3)
                cut(x + n // 3, y + n // 3 * 2, n // 3)
                cut(x + n // 3 * 2, y, n // 3)
                # 7, 8, 9
                cut(x + n // 3 * 2, y + n // 3, n // 3)
                cut(x + n // 3 * 2, y + n // 3 * 2, n // 3)
                return
            
    if num == -1:
        minus += 1
    elif num == 0:
        zero += 1
    elif num == 1:
        plus += 1


if __name__ == '__main__':
    n = int(sys.stdin.readline())
    paper = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

    minus, zero, plus = 0, 0, 0
    cut(0, 0, n)
    print(minus, zero, plus, sep='\n')