[Python] 백준 풀기 1780 - 종이의 개수

파이썬 백준 1780번

실버2

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

1780번: 종이의 개수

 

 

 

문제 보기

분류: 분할 정복, 재귀

 

 

 

문제 풀기

기존에 풀었던 2630번 문제 색종이 만들기와 같은 방식의 풀이이다.

https://xcevor.tistory.com/56

[Python] 백준 풀기 2630 - 색종이 만들기

차이가 있다면 기존 4 등분한 것을 가로 세로 각각 세 개로 나누어 총 9등분이 된다는 것이다.

매 분할마다 N 의 구간인 N//3*1 또는 N//3*2 을 x, y 에 잘 적용해 주면 된다.

그리고, -1, 0, 1 의 세 가지 경우에 대한 누적 합을 구한다.

 

입력 값에 대해서도 3의 거듭제곱 수로 나오지 않으면 예외를 두어야 하나 했으나 문제 자체에서 3^k 꼴로 주어진다 하여 별다른 조건을 추가시키지 않아도 된다.

 

조금씩 달라지는 반복 풀이를 진행하니 이런 문제에 대해 접근하는 것이 편해졌다.

 

 

 

코드 보기

import sys
inputdata = sys.stdin.readline

def fnPaperDivider(x, y, N):
    global count_minusone
    global count_zero
    global count_plusone
    
    num_check = paper_ls[x][y]
    
    for i in range(x, x + N):
        for j in range(y, y + N):
            if num_check != paper_ls[i][j]:
                fnPaperDivider(x, y, N//3)
                fnPaperDivider(x, y + N//3*1, N//3)
                fnPaperDivider(x, y + N//3*2, N//3)
                fnPaperDivider(x + N//3*1, y, N//3)
                fnPaperDivider(x + N//3*2, y, N//3)
                fnPaperDivider(x + N//3*1, y + N//3*1, N//3)
                fnPaperDivider(x + N//3*1, y + N//3*2, N//3)
                fnPaperDivider(x + N//3*2, y + N//3*1, N//3)
                fnPaperDivider(x + N//3*2, y + N//3*2, N//3)
                return
    
    if num_check == -1:
        count_minusone += 1
    elif num_check == 0:
        count_zero += 1
    elif num_check == 1:
        count_plusone += 1


if __name__ == "__main__":
    N = int(inputdata().strip())
    paper_ls = [list(map(int, inputdata().split())) for _ in range(N)]
    
    # print(N)          #
    # print(paper_ls)           #
    
    count_minusone = 0
    count_zero = 0
    count_plusone = 0
    
    fnPaperDivider(0, 0, N)
    
    print(count_minusone)
    print(count_zero)
    print(count_plusone)



# 9
# 0 0 0 1 1 1 -1 -1 -1
# 0 0 0 1 1 1 -1 -1 -1
# 0 0 0 1 1 1 -1 -1 -1
# 1 1 1 0 0 0 0 0 0
# 1 1 1 0 0 0 0 0 0
# 1 1 1 0 0 0 0 0 0
# 0 1 -1 0 1 -1 0 1 -1
# 0 -1 1 0 1 -1 0 1 -1
# 0 1 -1 1 0 -1 0 1 -1

# 10
# 12
# 11