[Python] 백준1780 종이의 개수

19 Jan 2023 in Study on Algorithm

백준1780 종이의 개수 링크

문제

예제 입력

---

코드

import sys

n = int(input())
arr = []
for _ in range(n):
    arr.append(list(map(int, sys.stdin.readline().split())))

ans = [0, 0, 0] # 0 1 -1
def sol(n, x, y):
    num = arr[x][y]

    for i in range(x, x + n):
        for j in range(y, y + n):
            if num != arr[i][j]:
                sol(n//3, x, y)
                sol(n//3, x, y + n//3)
                sol(n//3, x, y + 2*n//3)
                sol(n//3, x + n//3, y)
                sol(n//3, x + n//3, y + n//3)
                sol(n//3, x + n//3, y + 2*n//3)
                sol(n//3, x + 2*n//3, y)
                sol(n//3, x + 2*n//3, y + n//3)
                sol(n//3, x + 2*n//3, y + 2*n//3)
                return
    ans[num] += 1  

sol(n, 0, 0)
print(ans[-1])
print(ans[0])
print(ans[1])

설명

파이썬을 통해서 사용자로부터 입력받아 자료형 list를 사용하여 분할정복(재귀함수)알고리즘으로 종이의 개수를 구현했습니다.

---

결과