문제 링크
총 L명의 죄수를 G명의 간수가 관리하는 상황에서 위험도의 최솟값을 구하는 문제이다.
이를 dp로 표현하면
dp[g][l] : g명의 간수가 l번째 까지의 죄수를 관리할 때 최소 위험도
cost(i, j) : i번째부터 j번째 까지의 죄수를 한명의 간수가 관리할때 위험도
dp[g][l] = dp[g-1][k] + cost(k+1, l)
--> 위를 만족시키는 k를 구하는 문제로 변경시킬 수 있다.
l이 증가함에 따라 k는 같거나 증가한다. 왜냐하면 마지막 cost에 해당하는 죄수들의 명수가 늘어나기 때문에 k가 줄어들면 위험도가 올라간다.
따라서 분할정복을 이용한 동적계획법 최적화를 적용할 수 있다.
import java.io.*;
import java.util.*;
public class 탈옥 {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
L = Integer.parseInt(st.nextToken());//방개수
G = Integer.parseInt(st.nextToken());//간수 명수
sumCost = new long[L+1];
dp = new long[G+1][L+1];//[i][j]: i명의 간수가 j번째 죄수까지 관리할때 최소비용
st = new StringTokenizer(br.readLine());
sumCost[1] = Long.parseLong(st.nextToken());
for(int i = 2; i <= L; i++) sumCost[i] = Long.parseLong(st.nextToken()) + sumCost[i-1];
for(int l = 1; l <= L; l++)
dp[1][l] = cost(1, l);
for(int g = 2; g <= G; g++)
solve(g, 1, L, 1, L);
System.out.println(dp[G][L]);
}
static int L, G;
static long[] sumCost;
static long[][] dp;
static long MAX = 8000*8000*1000_000_000;
static void solve(int g, int lLow, int lHigh, int kLow, int kHigh){
if(lLow > lHigh || kLow > kHigh) return;
int lMid = (lLow + lHigh) >> 1;
int optK = kLow;
for(int k = kLow ; k <= Math.min(kHigh, lMid); k++){
long num = dp[g-1][k] + cost(k+1, lMid);
if(k == kLow || num < dp[g][lMid]){
dp[g][lMid] = num;
optK = k;
}
}
solve(g, lLow, lMid - 1, kLow, optK);
solve(g, lMid + 1, lHigh, optK, kHigh);
}
static long cost(int start, int end){ return (end - start + 1)*(sumCost[end] - sumCost[start - 1]);}
}