Hikenny25
1780 - 종이의 개수 본문
https://www.acmicpc.net/problem/1780
1780번: 종이의 개수
N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수
www.acmicpc.net
- 분할정복법
import sys
input = sys.stdin.readline
def divide(arr):
l = len(arr) // 3
for i in [0,l,2*l]:
for j in [0,l,2*l]:
check([row[j:j+l] for row in arr[i:i+l]])
def check(paper):
l = len(paper)
data = [[paper[0][0]] * l for _ in range(l)]
if data == paper:
cnt[paper[0][0] + 1] += 1
else:
divide(paper)
n = int(input())
matrix = list()
for _ in range(n):
matrix.append(list(map(int, input().split())))
cnt = [0,0,0] # -1, 0, 1
check(matrix)
for i in cnt:
print(i)
문제 해결 아이디어
1. 전체 검사
2. 같지 않다면 9분할 후 검사 / 같다면 카운트
사실 거의 2630 - 색종이 만들기 문제랑 같아서 빠르게 해결했다
'baekjoon (solved.ac) > class 3 Solve' 카테고리의 다른 글
| 2178 - 미로 탐색 (0) | 2022.10.30 |
|---|---|
| 17626 - Four Squares (1) | 2022.10.30 |
| 1074 - Z (0) | 2022.10.30 |
| 18870 - 좌표 압축 (0) | 2022.10.30 |
| 2630 - 색종이 만들기 (0) | 2022.10.29 |
'baekjoon (solved.ac)/class 3 Solve' Related Articles
more
Comments