[BOJ] 1780 종이의 개수 바로가기
N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다.
이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.
첫째 줄에 N(1 ≤ N ≤ 37, N은 3k 꼴)이 주어진다. 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다.
첫째 줄에 -1로만 채워진 종이의 개수를, 둘째 줄에 0으로만 채워진 종이의 개수를, 셋째 줄에 1로만 채워진 종이의 개수를 출력한다.
문제에서 주어진 규칙을 이용하여 알고리즘을 구현한다.
if check(x, y, N):
answer[graph[y][x]] += 1
return
def check(x, y, N):
std = graph[y][x]
for ny in range(y,y+N):
for nx in range(x,x+N):
if std != graph[ny][nx]:
return False
return True
graph
)의 x
~ x + N
구간, y
~ y + N
구간의 숫자가 모두 같다면 True
를 반환하고, 아닐 경우 False
를 반환한다.else:
N//=3
for dy in range(3):
for dx in range(3):
divideConquer(x+N*dx, y+N*dy, N)
# BOJ 1780 종이의 개수
# https://www.acmicpc.net/problem/1780
from sys import stdin
def solution(N, graph):
answer = {-1: 0, 0: 0, 1: 0}
# 종이가 모두 같은 수로 구성되어 있는가?
def check(x, y, N):
std = graph[y][x]
for ny in range(y,y+N):
for nx in range(x,x+N):
if std != graph[ny][nx]:
return False
return True
# 분할 정복
def divideConquer(x, y, N):
if check(x, y, N):
answer[graph[y][x]] += 1
return
# 같은 크기의 종이 9개로 분할
N//=3
for dy in range(3):
for dx in range(3):
divideConquer(x+N*dx, y+N*dy, N)
divideConquer(0, 0, N)
return answer.values()
N = int(stdin.readline())
graph = [list(map(int,stdin.readline().split())) for _ in range(N)]
result = solution(N, graph)
for res in result:
print(res)