조약돌( BOJ 25378 )

문제 : https://www.acmicpc.net/problem/25378

25378번: 조약돌

 

문제 파악하기

N개의 장소에 놓여진 조약돌을 2개의 작업으로 모두 가져오는 최소 횟수를 구하는 문제입니다. 두 작업은 임의의 개수를 가져올 수 있다고 했으나, 작업의 횟수를 최소로 해야하기 때문에 보통 하나 이상의 장소에 있는 모든 조약돌을 가져오는 작업이라고 할 수 있습니다. 아쉽게도 각 장소에 놓인 조약돌의 개수가 최대 10⁸개이기 때문에 단순한 재귀함수 및 메모이제이션으로 해결할 수 없습니다. 하지만, 우리는 작업 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]을 구하면 우리가 원하는 결괏값을 얻을 수 있습니다.

 

소스코드

 
#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]);
}
 

후기

전처리 과정을 통해 손쉽게 구할 수 있는 과정이 쉽사리 떠오르지 않았던 문제입니다. 정올에 출제된 동적 프로그래밍 문제답게 충분히 머리아프게 만들어주는 좋은 문제라고 생각합니다. 문법적인 내용도 어려운 점이 없기에 동적 프로그래밍을 연습하거나 올림피아드를 준비하는 사람에게 추천하고 싶은 문제입니다.