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공식을 찾아낼 수 있습니다!