1. 문제 설명
https://www.acmicpc.net/problem/2630
2630번: 색종이 만들기
첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다.
www.acmicpc.net
2. 아이디어
아예 분할 탐색을 쓰라고 문제에 사진까지 첨부해가며 어필하고 있다.
N = 2^k (1 <= k <= 7)이므로 N의 범위는 최대 128이 된다.
분할 탐색을 사용하면 시간복잡도가 해봐야 O(\(n^{2}log_{2}n\))이므로 충분히 통과할 수 있다.
3. 코드
cnt_w = 0
cnt_b = 0
def split(row, col, n, paper):
global cnt_w
global cnt_b
color = paper[row][col]
for y in range(row, row + n):
for x in range(col, col + n):
if (color != paper[y][x]):
split(row, col, n//2, paper)
split(row + n//2, col, n//2, paper)
split(row, col + n//2, n//2, paper)
split(row + n//2, col + n//2, n//2, paper)
return
if color == 0:
cnt_w += 1
else:
cnt_b += 1
def solution():
n = int(input())
paper = [list(map(int, input().split())) for _ in range(n)]
split(0, 0, n, paper)
print(cnt_w)
print(cnt_b)
solution()