백준13261 탈옥

작성일 | In

문제 링크

  • http://icpc.me/13261

사용 알고리즘

  • DP
  • Divide and Conquer Optimization

시간복잡도

  • O(GL log L)

풀이

Divide and Conquer Optimization을 모르신다면 (이 글) 을 먼저 봐주시기 바랍니다.

dp[t][i]를 t명의 간수가 i번 감옥까지 감시를 할 때, 탈옥 위험도의 최소값 이라고 정의합시다.
t번째 간수가 k+1부터 i번 감옥까지 감시를 한다면,
dp[t][i] = min(dp[t-1][k] + C[k+1][i]), (0 ≤ k ≤ i)이고,
C[k+1][i] = (sum[i] - sum[k]) * (i-k)입니다. (단, sum배열은 prefix sum입니다.)

이 점화식은 DnC Opt조건을 만족하기 때문에 최적화 기법을 적용할 수 있습니다.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll maxi = 1e16;
ll arr[8080], sum[8080];
ll dp[880][8080], p[880][8080];

inline ll cost(int i, int j){ return (sum[j] - sum[i-1]) * (j-i+1); }

void go(int t, ll l, ll r, ll pl, ll pr){
	if(l > r) return;
	int mid = (l + r) >> 1;
	dp[t][mid] = -1;
	p[t][mid] = -1;
	for(int k=pl; k<=pr; k++){
		ll tmp = dp[t-1][k] + cost(k+1, mid);
		if(dp[t][mid] == -1 || dp[t][mid] > tmp){
			dp[t][mid] = tmp;
			p[t][mid] = k;
		}
	}
	go(t, l, mid-1, pl, p[t][mid]);
	go(t, mid+1, r, p[t][mid], pr);
}

int main(){
	int m, n; cin >> m >> n; //감옥 크기, 간수 수
	for(int i=1; i<=m; i++){
		cin >> arr[i]; sum[i] = sum[i-1] + arr[i];
	}
	for(int i=0; i<=m; i++) dp[1][i] = cost(1, i), p[1][i] = 0;
	for(int t=2; t<=n; t++) go(t, 0, m, 0, m);

	cout << dp[n][m];
}