BOJ 12861 죄수에게 주는 뇌물

BOJ 12861 죄수에게 주는 뇌물

[분류 : 다이나믹 프로그래밍]

 

[풀이]

  [첫번째] 가장 처음에 Q[i]번째 죄수를 석방했다고 해보자. 그러면 1번째 죄수부터 Q[i]-1번째 죄수까지, Q[i]+1번째 죄수부터 P번째 죄수까지 모두 뇌물을 줘야한다.

  [그 이후의 석방] 이제 죄수를 고를 때 Q명의 죄수 중 i번째를 석방시켰으니, 이젠 구간을 나눠서 봐야한다. 

1. 구간 [1, Q[i]-1]에서 Q명의 죄수 중 누굴 석방할 것인지
2. 구간 [Q[i] + 1, P]에서 Q명의 죄수 중 누굴 석방할 것인지 

  [간단한 dp 아닌가 ?] 그러면 두 구간을 모두 다룰 수 있도록 구간 [l, r]에 대해 부분 문제를 (l, Q[i]- 1) + (Q[i]+1, r)로 두면 되지 않나? 싶은데, 모든 감옥을 인덱스로 담기에는 메모리나 시간이 부족하다.

  [Q의 인덱스] 남은 선택지는 Q의 인덱스 밖에 없으니 이걸로 dp 구간을 설정해보자.
  Q의 인덱스로 구성해야 한다면 위와 다르게 닫힌 구간이 아닌 열린구간 (l, r)로 봐야한다. Q[l]+1부터 Q[r]-1까지 죄수 중 [l+1, r-1] 구간에 있는 죄수를 석방할 수 있고, 거기서 어느 구간에 있는 죄수들에게 뇌물을 줘야하는지 바로 계산할 수 있다.
따라서 점화식은 아래처럼 구할 수 있다.

 

rec(l, r) = min i=[l+1,r-1] rec(l, i) + rec(i, r) + pos[r] - pos[l] - 2

 

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAX_N = 102;
int dp[MAX_N][MAX_N], pos[MAX_N];
int rec(int l, int r){
	if(l + 1 == r) return 0;
	int& ret = dp[l][r];
	if(ret != -1) return ret;
	ret = 1e9;
	for(int i=l+1;i<r;i++)
		ret = min(ret, rec(l, i) + rec(i, r) + pos[r] - pos[l] - 2);
	return ret;
}
int main() {
	memset(dp, -1, sizeof dp);
	int P, Q, i;
	scanf("%d%d",&P, &Q);
	pos[0] = 0, pos[Q+1] = P + 1;
	for(i=1;i<=Q;i++) scanf("%d",&pos[i]);
	sort(pos+1, pos+Q+1);
	printf("%d",rec(0, Q+1));
	return 0;
}