BOJ 백준 12861번 죄수에게 주는 뇌물

 

 

BOJ 백준 12861 죄수에게 주는 뇌물

 

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

12861번: 죄수에게 주는 뇌물

 

일렬로 된 P개의 감옥방에서 정해진 Q명의 죄수를 석방해야 한다. 어떤 한 죄수를 석방할 때 그 죄수 방의 바로 옆 방의 죄수들에게 뇌물을 줘야 하며, 옆 방의 또 옆 방에 있는 죄수들에게도 뇌물을 줘야 한다. 즉, 중간에 석방된 죄수로 인해 끊기는 지점 전까지 전달 가능한 죄수들에게 모두 금화 1개씩 뇌물로 줘야한다. Q명의 모든 죄수를 석방하기 위해 필요한 금화의 최소 개수를 구하는 것이 문제이다.

 

감옥방이 일렬로 나열되어 있으므로 현재 석방하려는 또는 이미 석방된 죄수가 수감된 방을 기준으로 금화를 전달해야 하는 구간이 나눠진다. 현재 석방하려는 죄수를 죄수 A라고 할 때, 죄수 A를 기준으로 왼쪽과 오른쪽이 나뉜다. 이미 석방된 죄수 방 중 죄수 A의 방에 가장 가까운 방들 중 왼쪽에 위치한 죄수의 번호를 left, 오른쪽에 위치한 죄수의 번호 right이라고 하자. 그리고 left번 죄수가 위치한 방 번호를 Left, right번 죄수가 위치한 방 번호를 Right라고 하자. 그러면 Left + 1부터 죄수 A의 방 바로 이전 번호까지는 구간 1이 되고, 죄수 A의 방 바로 이후 번호부터 Right - 1까지는 구간 2가 된다.

 

죄수 A를 석방하면 구간 1에서 다음 죄수를 골라서 석방하든가 아니면 구간 2에서 다음 죄수를 골라서 석방하든가 둘 중 하나를 택해야 하는데, 사실 둘 중에 어느 것을 먼저 택한다고 해서 필요한 금화 최소 개수가 달라지는 것은 아니다. 죄수 A를 석방하면서 나눠지는 구간 1과 2는 필요한 금화 개수에 관해 서로 독립적이다. 그래서 구간 1에서 어떤 죄수를 먼저 뽑든 간에 구간 2에서 죄수를 뽑는 순서에 영향을 끼치지 않는다. 그러므로 죄수를 석방하는 순서에 따라서 필요한 금화의 개수가 항상 반드시 달라진다고 볼 수 없으므로 석방 순서 자체에 너무 집착할 필요가 없어 보였다. 그래서 동적 프로그래밍(Dynamic Programming)을 사용하되 순서 자체를 메모이제이션하지는 않았다. (애초에 Q 값의 제한이 너무 커서 메모이제이션 가능하지도 않다.) 사실 구간을 나누고 고르는 과정에서 석방 순서가 결정된다. 다시 말해, 부분 문제로 나누어지는 과정에서 죄수들의 석방 순서가 자연스럽게 고려되는 것이다. 그러므로 동적 프로그래밍을 사용하여 순서까지 저장할 필요가 없다.

 

이미 Left와 Right을 알고 있고, Left에서 Right 사이 범위에는 이전에 석방된 죄수가 존재하지 않는다고 가정한다. 이 범위 내에서 석방 가능한 임의의 한 죄수의 번호를 i라고 하면, i는 left와 right 범위 안에 존재한다. 이를 종합하여 Left와 Right 구간 내 죄수들을 석방하는 데 필요한 금화의 총 개수는 다음과 같이 정리할 수 있다.

 

 

재귀로 구현하는 것이 효율적이라고 생각하여 go(left, right)이라는 함수를 만들었다. 그리고 메모이제이션을 위해 dp[left][right]이라는 배열에 go(left, right)의 반환 값을 저장했다.

 

 

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;


const int N_MAX = 100;
const int INF = 0x3f3f3f3f;


int p, q;
vector<int> a;
int dp[N_MAX + 2][N_MAX + 2];


int go(int left, int right) {
    if (left + 1 >= right){
        return 0;
    }
    
    int& ret = dp[left][right];
    if (ret != -1){
        return ret;
    }
    ret = INF;
    
    for (int i = left + 1; i < right; i++){
        ret = min(ret, go(left, i) + go(i, right) +
                  (a[right] - 1) - (a[left] + 1));
    }
    
    return ret;
}


int main(){
    memset(dp, -1, sizeof(dp));
    scanf("%d %d", &p, &q);
    
    a.push_back(0);
    for (int i = 1; i <= q; i++){
        int x; scanf("%d", &x);
        a.push_back(x);
    }
    a.push_back(p + 1);
    
    sort(a.begin(), a.end());
    
    int ans = go(0, q + 1);
    printf("%d\n", ans);
    
    return 0;
}