[분할정복] 백준 1780번 종이의 개수 with Python3

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

1780번: 종이의 개수

문제

 

내 풀이

import sys
input = sys.stdin.readline

N = int(input())
paper = [list(map(int, input().split())) for _ in range(N)]
one = 0
zero = 0
minus = 0


def nine_tree(x, y, n):
    global one, zero, minus, color
    color = paper[y][x]
    double_break = False
    third_n = n//3

    for i in range(x, x+n):
        if double_break:
            break

        for j in range(y, y + n):
            if paper[j][i] != color:
                nine_tree(x, y, third_n)
                nine_tree(x+third_n, y, third_n)
                nine_tree(x+(third_n*2), y, third_n)

                nine_tree(x, y+third_n, third_n)
                nine_tree(x+third_n, y+third_n, third_n)
                nine_tree(x+(third_n*2), y+third_n, third_n)

                nine_tree(x, y+(third_n*2), third_n)
                nine_tree(x+third_n, y+(third_n*2), third_n)
                nine_tree(x+(third_n*2), y+(third_n*2), third_n)
                double_break = True
                break

    if not double_break:
        if paper[y][x] == 1:
            one += 1
        elif paper[y][x] == 0:
            zero += 1
        else:
            minus += 1


nine_tree(0, 0, N)
print(minus)
print(zero)
print(one)

해설

색종이 만들기를 거의 복붙하듯이 풀었다. 사실상 같은 개념이었지만 분할만 더욱 많았을 뿐인 문제였던거 같다.

 

https://bdbest.tistory.com/88?category=964851