dp를 찾는 방법. [interval dp], 백준 11066번
dp는 상황을 나누고, 그 간의 관계를 파악하여 점화식 혹은 a=b와 같은 고정된 수식으로 표현하여 문제를 효율적으로
해결하는 방식이다.
예를 들어 동전이 연속으로 앞면이 나올 확률을 구한다고 생각해보자.
모든 상황은 결국 나누면 앞면, 뒷면 으로 나뉜다. 이를 수식으로 표현해보자.
n-1 째까지 앞면 나올 확률 * 앞면 나올 확률 = n 째까지 앞면 나올 확률
즉 f(n-1)* 1/2 = f(n) 이라는 점화식을 구할 수 있다.
dp는 이런 특정 행동 (동전을 던짐) 에 따른 관계의 변화를 수식으로 표현해서 구할 수 있다.
(특정행동 n-1번 = 특정행동 n번 이런식으로 생각하면 쉽다.)
전에 knapsack 알고리즘에 대해서도 정리했었는데, dp라고 생각하고 식을 구해도 해결할 수 있다.
추가로 interval dp 라는 dp에 대한 설명과 dp를 구하는 과정을 통해 dp 공식을 찾는 방법을 연습해보자.
기존에 우리가 쓰던 dp[i] 배열은 보통 아래와 같다.
dp [i] 0~i 째 까지의 값을 확인 했을 시, 정답(최대 혹은 최소 등 어떠한 값)
하지만 만약 특정 구간에 대한 값을 알고 싶다면 어떻게 해야할까?
구간에 대한 dp에서 사용하는 배열은 아래와 같다.
dp[i][j] 가 i~j 구간의 정답(최대, 최소 등 어떠한 값)
보통 모든 가능한 i~j 범위를 구하기 위해 모든 점들을 시작번호로 둘 수있는 for 문 1개, 모든 간격의 길이를 가질 수 있게하는 for 문 한개가 필요하다.
ex) 시작점 3, 간격의 길이 5 일 경우 3,4,5,6,7 즉 3~7 시작점 1, 간격의 길이 2 인 경우 1,2 즉 1~2 이런식.
따라서 모든 구간에 대한 case를 탐색하는 데에 2중 for문을 사용하게 된다.
실전 예시로 백준 11066번 문제를 읽어본 뒤 아래 코드를 같이 살펴보자.
(+)
처음에 '인접한 파일만 합칠 수 있다' 를 못보고 크기가 작은순으로 합치게 구현했다가 다시 짰다.. 잘못 짠 코드는 위에 주석처리된 main 문이니 interval dp만 보고 싶다면 무시하시길...
#include<iostream>
#include<queue>
#include<functional>
#include<algorithm>
#include<string.h>
using namespace std;
/*
int main() {
int t,k;
cin >> t;
while (t--) {
priority_queue<int,vector<int>,greater<int>> pq;
cin >> k;
int tmp,ans=0;
for (int i = 0; i < k; i++) {
cin >> tmp;
pq.push(tmp);
}
while (!pq.empty()) {
int a = pq.top();
pq.pop();
if (pq.empty())
break;
int b = pq.top();
pq.pop();
pq.push(a + b);
ans += (a + b);
}
cout << ans << endl;
}
}
*/
//위의 풀이는 '서로 인접한 파일들끼리만 합칠수 있다.' 라는 조건 못보고 푼것
const int inf = 987654321;
int main() {
int t, k;
cin >> t;
while (t--) {
int dp[501][501],sum[501],cost[501];
memset(dp, 0, sizeof dp);
memset(sum, 0, sizeof sum);
cin >> k;
for (int i = 1; i <= k; i++) {
cin >> cost[i];//i까지 합쳤을때 비용
sum[i] += (sum[i - 1]+cost[i]);
}
//(i<=mid<j)
//간격(범위)가 1,2,...... ,시작점이 1,2,3, .... k-1 인 모든 범위 tx,ty 를 탐색하는 이중for문
for (int d = 1; d < k; ++d) {//tx, ty의 간격 바로옆, 2칸옆,......k-1칸옆까지.
for (int tx = 1; tx + d <= k; ++tx) {
int ty = tx + d;
dp[tx][ty] = inf;//안해주면 0값이 무조건 최소로 들어가게된다.
//이 아래의 for문은 dp[tx][ty] 를 찾는 for문
for (int idx = tx; idx < ty; ++idx)
dp[tx][ty] =
min(dp[tx][ty], dp[tx][idx] + dp[idx + 1][ty] + sum[ty] - sum[tx - 1]);
}//초반 1칸옆의 경우를 완수할때, sum값들로만 구성해야됨. 따라서 0으로 초기화한것.
}//
cout << dp[1][k ] << endl;
}
}for( int d ~~~ ) : 어떠한 시작점에서 d개의 파일에 대한 구간 길이에 대한 for문 ( 시작점 ~ 시작점 +(d-1) )
for(int tx~~~~ ) : 시작점에 대한 for문
dp[tx][idx] + dp[idx+1][ty] >> tx ~ idx 범위 최소값 + idx+1 ~ ty 범위 최소값
sum[ty]-sum[tx-1] >> tx~ ty 의 구간합. ( sum[i]: 0~i 까지 누적합. sum[n-1] +n째 cost = sum[n] )
이는 tx~ ty 범위 내의 파일을 하나의 파일로 합치는 비용
i~ j째 구간의 파일 크기가10, 20 ,30 ,40 라고 가정해보자. 최소라는 조건은 우선 배제하고 파일합을 구하려면, 한가지 방식으론
10, 20 을 합치고, 30, 40 을 합치는 방식이 있다. 이때 i ~ i+1 째 의 파일합, i+2 ~ i+3 째 파일합이 사용된다.
이 부분이 dp[tx][idx] + dp[idx+1][ty] 로 표현된다.
그리고 마지막으로, 30, 70 을 압축된 2개의 파일을 합쳐야 하는데, 이는 주어진 10,20,30,40 을 모두합친 값이다.
이 부분이 sum[ty]-sum[tx-1] 로 표현된다.
즉 위 코드의 dp가 의미하는 것은 아래와 같다.
기존에 구했던 tx~ty 파일합 최소 = min( 기존 파일합, tx~idx / idx~ ty 의 지점에서 합쳤을 때 새롭게 갱신되는 파일합 )
최소, 최대 이런 문자를 배제하고 주어진 상황을 구하는 과정을 가장 낮은 지점부터 생각해 나간다면 상대적으로 쉽게 dp공식을 찾아낼 수 있습니다!