취준/백준
[백준][Python][1780][분할정복] 종이의 개수
puff
2020. 2. 16. 13:43
문제 : https://www.acmicpc.net/problem/1780
1780번: 종이의 개수
N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다. (1)이 아닌 경우에는 종이를 같은 크기의 9개의 종이로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다. 이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으
www.acmicpc.net
분할정복 문제다.
종이를 -1,0,1로 나눴으니 +1 을 하면 리스트의 인덱스로 쓸수 있겠다 싶었다.
이 문제는 두개의 함수로 나눌수 있다.
- lastpaper(x,y,size)
- 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]))