1780: 종이의 개수
분할정복의 대표 문제로 분할정복 알고리즘에 대해서 알아보자!
분할정복이란?
기존 문제를 작은 부분문제로 나눔 원래 문제와 성격이 동일하고, 분할된 작은 문제는 입력 크기만 작아진 것이다. 분할된 문제는 서로 독립적이라는 특징이 있고, 분할 정복 알고리즘을 3단계로 나눠볼 수 있다.
1. 분할: 문제의 입력들을 작은 사례로 분할하는 것. 기존의 문제 입력들과 똑같은 성격을 가지고 있다.
- 분할 내 세부 케이스로 Base case, Recursive case로 나눌 수 있는데 다음과 같다.
a. Base case: 이미 문제가 충분히 작아서, 더 작은 부분문제로 나누지 않아도 바로 문제를 알 수 있는 경우
b. Recursive case: 문제가 커서 바로 답을 몰라 같은 형태의 부분 문제들로 쪼개서 풀어야하는경우 - 분할 과정을 통해 해결한다.
2. 정복: 작은 입력들이 충분히 작지 않으면 재귀 호출한다. 각 부분 문제를 해결
3. 병합: 부분 문제 솔루션을 통해 전체 문제 해결
한마디로 재귀적으로 자신을 호출하면서 연산의 단위를 줄여가는 알고리즘으로 이해하면 된다. 분할정복의 사례가 많은데, 이진탐색, 퀵정렬도 분할 정복의 예시이다. 그렇지만 이진 탐색 알고리즘에서는 병합 과정이 없음!
유사문제로 2630번이 있는데 2630 문제를 이해하면 1780번도 쉽게 이해할 수 있다. 백준 2630 색종이 만들기를 살펴보자!
https://www.acmicpc.net/problem/2630
첫 색상이 나머지 색상과 같은지 확인 후 틀린 것이 있으면, 틀린 구역을 다시 네 구역으로 나누어 다시 색상이 같은 것을 확인해준다. 재귀호출시 들어가야할 인수의 값은 색종이의 시작점이 되고, 한번 분할할 때마다 길이는 반으로 줄고 반으로 줄은 길이만큼 각 x,y에 더해주면 된다. 하얀색으로 칠해진 색종이와 파란색으로 칠해진 색종이 각각에 대한 개수 구해야 하므로 각각을 세주는 변수를 만들어서 count +1해주었다.
[사진첨부]
import sys
N = int(sys.stdin.readline())
paper = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
blue_cnt = 0
white_cnt = 0
def solution(x, y, N) :
global blue_cnt, white_cnt
color = paper[x][y]
for i in range(x, x+N) :
for j in range(y, y+N) :
if color != paper[i][j] :
solution(x, y, N//2) #1
solution(x, y+N//2, N//2) #2
solution(x+N//2, y, N//2) #3
solution(x+N//2, y+N//2, N//2) #4
return
if color == 0 :
white_cnt += 1
else :
blue_cnt += 1
solution(0,0,N)
print(white_cnt)
print(blue_cnt)문제
N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다.
- 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
- (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.
이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.
입력
첫째 줄에 N(1 ≤ N ≤ 37, N은 3k 꼴)이 주어진다. 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다.
출력
첫째 줄에 -1로만 채워진 종이의 개수를, 둘째 줄에 0으로만 채워진 종이의 개수를, 셋째 줄에 1로만 채워진 종이의 개수를 출력한다.
예제 입력 1
9
0 0 0 1 1 1 -1 -1 -1
0 0 0 1 1 1 -1 -1 -1
0 0 0 1 1 1 -1 -1 -1
1 1 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0
0 1 -1 0 1 -1 0 1 -1
0 -1 1 0 1 -1 0 1 -1
0 1 -1 1 0 -1 0 1 -1
예제 출력 1
10
12
11해설 및 코드:
import sys
n = int(sys.stdin.readline())
paper = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
minus_cnt, zero_cnt, plus_cnt = 0, 0, 0
def sol(x, y, n):
global minus_cnt, zero_cnt, plus_cnt
numbers = paper[x][y]
for i in range(x, x + n):
for j in range(y, y + n):
if numbers != paper[i][j]:
nxt_n = n // 3
sol(x, y, nxt_n) # 1
sol(x, y + nxt_n, nxt_n) # 2
sol(x, y + (2 * nxt_n), nxt_n) # 3
sol(x + nxt_n, y, nxt_n) # 4
sol(x + nxt_n, y + nxt_n, nxt_n) # 5
sol(x + nxt_n, y + (2 * nxt_n), nxt_n) # 6
sol(x + (2 * nxt_n), y, nxt_n) # 7
sol(x + (2 * nxt_n), y + nxt_n, nxt_n) # 8
sol(x + (2 * nxt_n), y + (2 * nxt_n), nxt_n) # 9
return
if numbers == -1:
minus_cnt += 1
elif numbers == 0:
zero_cnt += 1
elif numbers == 1:
plus_cnt += 1
return
sol(0, 0, n)
print(minus_cnt)
print(zero_cnt)
print(plus_cnt)