[파이썬] 백준 1780 : 종이의 개수

[파이썬] 백준 1780 : 종이의 개수

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

1780번: 종이의 개수

실버 2

분할정복, 재귀

---

접근

이 문제를 풀기전에 백준의 색종이 만들기 문제를 먼저 풀어보는 것이 좋다.

https://afterdawncoding.tistory.com/145

[파이썬] 백준 2630 : 색종이 만들기

색종이 만들기에서 4번 쪼개기 위해 재귀함수를 4번 사용한 것처럼 이 문제에서도 동일 한 크기의 종이 9개로 자르기 때문에 재귀함수를 9번 사용하면 된다.

x축, x축+1/3, x축+2/3지점과

y축, y축+1/3, y축+2/3지점의 모든 경우에 대한 재귀함수를 적용하면 쉽게 풀어낼 수 있다.

 

코드 1 (5408ms)

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

def solution(x, y, N):   
    global minus, zero, one
    color = paper[x][y]    
    for i in range(x, x+N):    
        for j in range(y, y+N):
            if color != paper[i][j]:    
                next_n = N//3
                solution(x, y, next_n) 
                solution(x+next_n, y, next_n) 
                solution(x+(next_n*2), y, next_n) 
                solution(x, y+next_n, next_n) 
                solution(x, y+(next_n*2), next_n) 
                solution(x+next_n, y+next_n, next_n) 
                solution(x+(next_n*2), y+next_n, next_n) 
                solution(x+next_n, y+(next_n*2), next_n) 
                solution(x+(next_n*2), y+(next_n*2), next_n) 
                return
    
    if color == 0:    
        zero += 1
    elif color == 1:
        one += 1
    elif color == -1:
        minus += 1

solution(0, 0, N)
print(f'{minus}\n{zero}\n{one}')

 

코드 2 (6444ms)

모든 경우에 대해 이중반복문으로 재귀함수 처리를 한다. 다만 처리 속도는 더 많이 걸린다.

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

def solution(x, y, N):   
    global minus, zero, one
    color = paper[x][y]    
    for i in range(x, x+N):    
        for j in range(y, y+N):
            if color != paper[i][j]:    
                for k in range(3):
                    for l in range(3):
                        solution(x+k*N//3, y+l*N//3, N//3) 
                return    
    
    if color == 0:    
        zero += 1
    elif color == 1:
        one += 1
    elif color == -1:
        minus += 1

solution(0, 0, N)
print(f'{minus}\n{zero}\n{one}')