조약돌( BOJ 25378 )
문제 : https://www.acmicpc.net/problem/25378
25378번: 조약돌
좌우 한 줄로 있는 N개의 장소 각각에 조약돌이 몇 개씩 놓여 있다. 철수가 할 수 있는 작업의 종류는 아래 두 가지이다. 인접한 두 장소에서 임의의 동일한 개수의 조약돌을 가져가기 한 장소에
www.acmicpc.net
문제 파악하기
N개의 장소에 놓여진 조약돌을 2개의 작업으로 모두 가져오는 최소 횟수를 구하는 문제입니다. 두 작업은 임의의 개수를 가져올 수 있다고 했으나, 작업의 횟수를 최소로 해야하기 때문에 보통 하나 이상의 장소에 있는 모든 조약돌을 가져오는 작업이라고 할 수 있습니다. 아쉽게도 각 장소에 놓인 조약돌의 개수가 최대 108개이기 때문에 단순한 재귀함수 및 메모이제이션으로 해결할 수 없습니다. 하지만, 우리는 작업 1의 특성을 활용하면 문제를 해결할 수 있습니다.
문제 해결하기
우리는 N개의 장소에 있는 모든 조약돌은 작업 2를 활용하면 최대 N번만에 가져올 수 있다는 사실을 파악할 수 있습니다. 또한, 작업 1을 적절하게 활용하면 N번의 작업 횟수가 줄어들 수 있다는 점을 유추할 수 있습니다. 만약 (l, r) 구간 내의 모든 조약돌을 작업 1로 처리할 수 있다면 (r-l)번만에 모든 조약돌을 가져올 수 있기 때문입니다. 작업 2을 사용하여 가져온다면 (r-l+1)번으로 작업 1보다 1회 더 많습니다. 따라서, 우리는 구간 (l, r)에서 작업 1을 통해 모든 조약돌을 가져올 수 있는지 파악하고, 이를 통해 N개의 조약돌을 모두 가져오는 작업의 최소 횟수를 구할 수 있습니다.
여기서 필요한 단계는 크게 2가지 입니다. 첫 번째, 각각의 구간에서 작업 1을 통해 모든 조약돌을 가져올 수 있는지 파악하는 단계입니다. 중첩 반복문을 사용하여 나올 수 있는 모든 구간에서 조약돌을 작업 1만으로 가져올 수 있다면 1 / 가져올 수 없다면 0을 확인한 다음, 저장해놓으면 됩니다. 그러면 다음 단계인 실제 작업 횟수의 최솟값을 구할 때 활용할 수 있습니다. 두 번째, 이전에 확인했던 값을 바탕으로 현재 장소까지 모든 조약돌을 가져오는데 필요한 최소 횟수를 구하면 됩니다. 이 때에는 다음 점화식을 활용할 수 있습니다.
dp[ idx ] = min( dp[idx-1]+1, ( check[l][r]가 1인 구간 중 dp[l-1] + (r-l)의 최솟값 ) )
이렇게 점화식을 활용하면 문제를 해결할 수 있는 소스코드를 손쉽게 작성할 수 있습니다. [ dp[idx-1]+1 ]은 (1, idx-1)까지 최소 횟수로 조약돌을 가져간 다음, 작업 2로 idx번째 장소의 모든 조약돌을 가져간 횟수를 의미합니다. [ dp[l-1] + (r-l) ]은 (1, l-1)까지 최소 횟수로 조약돌을 가져간 다음, (l, r)의 모든 조약돌은 작업 1을 통해 가져간 횟수를 의미합니다. 이렇게 dp[idx]가 나올 수 있는 경우의 수를 파악한 다음, 최종적으로 dp[N]을 구하면 우리가 원하는 결괏값을 얻을 수 있습니다.
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#define NMAX 2510
#define INF 987654321
using namespace std;
int N;
int inp[NMAX];
int ans[NMAX];
int check[NMAX][NMAX];
int main() {
// input
scanf("%d", &N);
for(int i=1;i<=N;i++) scanf("%d", &inp[i]);
// (l, r)까지 작업 1을 해서 모두 가져갈 수 있는지 여부
for(int l=1;l<N;l++) {
int f = 1;
int bef = inp[l];
for(int r=l+1;r<=N;r++) {
if(bef == inp[r]) check[l][r] = f;
else {
check[l][r] = 0;
if(bef > inp[r]) f = 0;
}
bef = abs(bef - inp[r]);
}
}
// solve
ans[1] = 1;
for(int r=2;r<=N;r++) {
ans[r] = ans[r-1]+1;
for(int l=1;l<r;l++) {
if(!check[l][r]) continue;
// ans[l-1] + (r-l): (1, l-1)까지의 최솟값 + 2번 작업 (r-l)회
ans[r] = min( ans[r], ans[l-1] + (r-l) );
}
}
printf("%d", ans[N]);
}
|
cs |
후기
전처리 과정을 통해 손쉽게 구할 수 있는 과정이 쉽사리 떠오르지 않았던 문제입니다. 정올에 출제된 동적 프로그래밍 문제답게 충분히 머리아프게 만들어주는 좋은 문제라고 생각합니다. 문법적인 내용도 어려운 점이 없기에 동적 프로그래밍을 연습하거나 올림피아드를 준비하는 사람에게 추천하고 싶은 문제입니다.