개발/algorithm
[백준 1780번] 종이의 개수 - python
zzi_on2
2022. 2. 15. 15:31
문제 링크
https://www.acmicpc.net/problem/1780
1780번: 종이의 개수
N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수
www.acmicpc.net
풀이
- 앞서 백준 색종이 만들기 문제를 통해 분할 정복 문제를 풀어보았더니 쉽게 풀 수 있었다.
https://zzion2.tistory.com/170
[백준 2630번] 색종이 만들기 - python
문제 링크 https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들..
zzion2.tistory.com
- 이번에는 3등분으로 분할하여 재귀적으로 호출
result = []
def sol(x, y, n):
start = graph[x][y]
for i in range(x, x+n):
for j in range(y, y+n):
# 종이가 같은 수가 아니면
if graph[i][j] != start :
sol(x, y, n//3)
sol(x, y + n//3, n//3)
sol(x, y +2 * (n//3) , n//3)
sol(x + n//3, y, n//3)
sol(x + n//3, y + n//3 , n//3)
sol(x + n//3, y + 2 * (n//3), n//3)
sol(x + 2 * (n//3), y, n//3)
sol(x + 2 * (n//3), y + n//3, n//3)
sol(x + 2 * (n//3), y + 2 * (n//3), n//3)
return
if start == -1:
result.append(-1)
if start == 0:
result.append(0)
if start == 1 :
result.append(1)
n = int(input())
graph = []
for _ in range(n):
graph.append(list(map(int,input().split())))
sol(0,0,n)
print(result.count(-1))
print(result.count(0))
print(result.count(1))