백준/문제풀이_python
1780 종이의 개수
휴대용치즈
2023. 1. 4. 22:41
https://www.acmicpc.net/problem/1780
1780번: 종이의 개수
N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수
www.acmicpc.net
문제 접근
분할정복 문제다.
다른 분할탐색 실버문제는 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