[백준][Python][1780][분할정복] 종이의 개수

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

1780번: 종이의 개수

분할정복 문제다. 

종이를 -1,0,1로 나눴으니 +1 을 하면 리스트의 인덱스로 쓸수 있겠다 싶었다.

 

이 문제는 두개의 함수로 나눌수 있다.

1. lastpaper(x,y,size)
2. numpaper(size,x,y)

lastpaper 함수는 x,y를 시작으로 size 만큼 돌면서 이 사각형이 같은 종이인지 판별하고, 종이의 숫자를 파악한다.

 

numpaper 함수는 재귀함수로 모든 종이를 0,0에서부터 돌면서 lastpaper 가 같은 종이인지 판별한걸 가지고 

• 종이가 완전하게 한장이면 -> 그대로 ans 에 +1, 그리고 다음 종이 확인
• 1/3을 해야 한장이 되는지 -> size//3 해서 확인한다.

 

 

import sys
from operator import add
ans = [0,0,0]
data = []
temp = 0
n = int(input())
for i in range(n):
    data.append([int(i) for i in sys.stdin.readline().rstrip().split()])

def lastpaper(x,y,size):
    global ans
    tmpans = [0,0,0]
    init = data[x][y]
    sameflag = True
    for i in range(size):
        for j in range(size):
            if data[x+i][y+j]!= init:
                sameflag = False
                break


    return sameflag,init

def numpaper(size,x,y):
    global ans
    
    gflag,i = lastpaper(x,y,size)
    if gflag:
        ans[i+1] +=1
    else:
        for i in range(3):
            for j in range(3):

                numpaper(size//3, x+ i*(size//3),y+ j*(size//3))

numpaper(n,0,0)
print("{}\n{}\n{}".format(ans[0],ans[1],ans[2]))