1780 종이의 개수

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

1780번: 종이의 개수

 

 

 

 

 

 

 

 

 

 

 

 

 

 

문제 접근

분할정복 문제다.

다른 분할탐색 실버문제는 4개로 나눴지만 이문제에선 9개로 나눈다.

재귀를 활용해서 9번 쪼개면 끝

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

코드

import sys
input = sys.stdin.readline

"""
분할정복
size//3을 0번, 1번, 2번 더하는걸 반복하면서 9개로 쪼개기.

"""

minus = 0
zero = 0
plus = 0

def rec(x, y, size):
    num = arr[x][y]
    for i in range(x, x+size):
        for j in range(y, y+size):
            if num != arr[i][j]:
                #9개로 쪼개기
                rec(x, y, size//3)
                rec(x, y + size//3, size//3)
                rec(x, y + (size//3*2), size//3)
                rec(x + size//3, y,size//3)
                rec(x + size//3,y + size//3, size//3)
                rec(x + size//3,y + (size//3*2), size//3)
                rec(x + (size//3*2), y ,size//3)
                rec(x + (size//3*2), y + size//3, size//3)
                rec(x + (size//3*2), y + (size//3*2), size//3)
                return 
    if num == -1:
        global minus
        minus += 1
    elif num == 0:
        global zero
        zero += 1
    else:
        global plus
        plus += 1

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

rec(0, 0, N)
print(minus, zero, plus, end="\n")

69424KB 4472ms