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

문제 링크

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

2630번: 색종이 만들기

풀이

def count_paper(n):
    count = [0, 0]

    def recursion(n, x, y):
        total = sum([paper[y+yy][x+xx] for yy in range(n) for xx in range(n)])
        if total == 0: count[0] += 1
        elif total == n*n: count[1] += 1
        else:
            n //= 2
            recursion(n, x, y)
            recursion(n, x+n, y)
            recursion(n, x, y+n)
            recursion(n, x+n, y+n)

    recursion(n, 0, 0)
    print(count[0])
    print(count[1])

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

recursion의 매개변수 n은 현재 종이의 길이, x와 y는 현재 종이의 좌측 상단의 좌표이다.

recursion을 호출하면 가장 먼저 현재 커버하고 있는 범위의 수를 모두 더하였을 때 0이면 흰색 종이의 개수를 증가시키고, n*n이면 파란색 종이의 개수를 증가시키고, 그 외에는 종이를 4분할하여 재귀호출하였다.

 

 

다른 언어로 된 풀이

[백준 2630] 색종이 만들기 with Node.js