구간 dp 정리 (interval dp)

구간 dp

 

기본적인 dp 는 보통 아래와 같이 시작~ 끝지점까지를 구하는 것으로 '전체의 최대 or 최소'를 찾는다.

dp[n] =>  0~n까지의 최대or 최소

 

하지만, 이런식으로는 해결하지 못하는 문제도 존재한다.

만약 시작점-끝점이 아닌,   '구간'에 대해 최소 or 최대 등을 bottom-up 방식으로 dp로 풀어나가기 위해선 이중배열을 기반으로 구간 dp를 구성해야한다.

 

구간 dp의 반복문은 보통 아래와 같다.

for( 구간의 길이)
	for(시작점~ 시작점-길이 )// 시작점 선택 ->  ( 끝점 = 시작+길이이기에 자동으로 시작~ 끝 구간 선택 가능)

bottom-up 을 수행해야하기에, '구간의 길이' 가 커지는 순서로 구성해야한다.

그래야   1~3 구간을 [1~1], [2~2], [3~3], [1~2], [2~3]  와 같은 하위 구간들로 갱신할 수 있기 때문이다.

 

 

문제 모음

문제 링크1

https://www.acmicpc.net/status?user_id=shyswy&problem_id=11066&from_mine=1 

채점 현황

문제 풀이

'서로 인접한 파일 끼리만 합칠 수 있다' 라는 조건이 중요하다.

 

즉 파일이 합쳐지는 모든 상황을 '왼쪽 파일 과 오른쪽 파일을 합치는 것' 으로 단순화할 수 있다.

 

이를 통해 A,B 파일 합치는 값 = A,B를 총합한 크기 + (A파일을 만들기 위해 든 비용) + (B 파일을 만드는데 드는 비용) 으로 표현할 수 있다.

 

이를 기반으로 다음과 같은 dp를 구성했다.

dp[i][j]: i~j까지 파일을 합치는데 드는 비용.

dp[i][j]=   dp[i][poiint] + dp[point+1][j] + [i~j] 구간의 파일 총 크기;
//'왼쪽 파일 만드는데 든 비용 + 오른쪽 파일을 만드는데 드는 비용 + 전체 파일 크기 '

 

정답 코드

#include<iostream>
#include<vector>
using namespace std;
#include<string.h>
int dp[501][501];
int sum[501];
int main() {
	int t;
	cin >> t;
	while (t--) {
		int k;
		vector<int> files;
		cin >> k;
		memset(dp, 9876543, sizeof(int) * 501 * 501);
		memset(sum, 0, sizeof(int) * 501);
		for (int i = 0; i < k; i++) {
			int tmp;
			cin >> tmp;
			files.push_back(tmp);
		}
		
		//d[i][j] i~j까지의 파일 합치는데 드는 비용 최소 
		sum[0] = files[0];
		for (int i = 0; i < files.size(); i++) {
			dp[i][i] = 0;
			if(i!=files.size()-1)
				sum[i + 1] = sum[i] + files[i + 1];
		}
		for (int len =1 ; len < files.size(); len++) {
			for (int st = 0; st + len < files.size(); st++) {
				int ed = st + len;
				for (int i = st; i <ed; i++) {
					int interval_sum;
					if (st - 1 < 0) {
						interval_sum = sum[ed];
					}
					else interval_sum= sum[ed] - sum[st - 1];
					dp[st][ed]=min(dp[st][ed], dp[st][i] + dp[i + 1][ed] + interval_sum);
						
				}
			}

		}
		cout << dp[0][files.size() - 1] << endl;
	}
}

 

TroubleShooting
처음에 아래와 같이 잘못 된 dp 공식을 세웠다.
dp[i][j]=   dp[i][poiint] + (  dp[i][poiint] + dp[point+1][j] ) +  dp[point+1][j]  ;
dp[i][j] == [i~j] 까지 파일을 합치는데 드는 '총 비용' 이지 i~j 사이의 파일 크기가 아닌 것을 망각하고 삽질을 조금 했다..
항상 dp를 세울 때는, 해당 dp가 정확하게 '무엇' 을 표현하는지 명확하게 생각하자!

 

 

 

문제 링크2

https://school.programmers.co.kr/learn/courses/30/lessons/1843

프로그래머스

 

문제 풀이

 

가능한 모든 구간 i~j 를  '길이 순'으로 탐색하여 bottom-up   dp를 수행해야한다.

그리고 주어진 구간 i~j 에 대해,   해당 구간을 내포 중인 모든 연산자를 기준으로 나누어서 dp 값을 갱신해야한다.

 

ex) 아래의 0~3 구간 이 선택된 경우 아래와 같이 나눌 수 있다.

1-2+3-4  ->   [1] - [2+3-4]  , [1-2] + [3+4], [1-2+3] - [4] 

 

위와 같이 나누어 놓는다면 A + B 혹은 A-B 두가지 형태로 모든 경우의 수를 표현할 수 있다.

•  A+B 꼴이 나오면 A의 최대 + B의 최대 == A,B 전 구간의 최대
• A-B 꼴이 나오면 A구간의 최대 - B 구간의 최소 == A,B 전 구간의 최대

따라서 우리는 구간에서 주어진 숫자로 만들 수 있는 최소, 최대 값을 dp로 유치해야한다.

 

dp식
max_dp[i][j]: i쨰 수 ~ j째 수 사이의 수식을 통해 만들 수 있는 최댓값
min_dp[i][j]: i쨰 수 ~ j째 수 사이의 수식을 통해 만들 수 있는 최댓값

 

예시 ( idx는 0번부터 시작)
1 - 2 - 3 - 4 
dp[1][3]==  (2 - 3 - 4) 에서 우리가 괄호를 마음대로 쳐서 구할 수 있는 수의 최댓값 == 2-(3-4)   =>3

 

반복문 구성

for( 숫자 구간의 길이)
	for(시작 숫자 선택 )// 시작, 끝점 선택( 끝점 = 시작+길이) == 숫자 구간 선택
    	for( 해당 구간의 모든 연산자 기준으로 dp 갱신 ){ //
        
        
        }

 

정답 코드

 

#include <vector>
#include <string>
#include<math.h>
#include<iostream>
using namespace std;

int max_dp[510][510];
int min_dp[510][510];
int solution(vector<string> arr)
{
    int answer = -1;
    for(int i=0;i<510;i++){
        for(int j=0;j<510;j++){
            max_dp[i][j]=-987654321;
            min_dp[i][j]=987654321;
        }
    }
    vector<int> nums;
    vector<string>ops;
    nums.push_back(stoi(arr[0]));
    for(int i=1;i<arr.size();i+=2){
         ops.push_back(arr[i]);
         nums.push_back(stoi(arr[i+1]));
    }

    for(int i=0;i<nums.size();i++){
            max_dp[i][i]=nums[i];
            min_dp[i][i]=nums[i];
    }
    
    for (int len = 1; len <=nums.size(); len++) { //길이
		for (int i=0;i<= nums.size() -len;i++){ //시작점~ 종료 구간 
			int st = i, ed = st + len-1;
			for (int it = st; it < ed  ; it++) { //위의 구간에서 기준이되는 연산자 정하기 
			//  [   ]  op  [  ] 의 최대, 최소 찾기 
				if (ops[it] == "-") {
                    max_dp[st][ed]=max(max_dp[st][ed],max_dp[st][it]-min_dp[it+1][ed]);
                    min_dp[st][ed]=min( min_dp[st][ed],min_dp[st][it]-max_dp[it+1][ed]);
				}
                else{
                    max_dp[st][ed]=max(max_dp[st][ed],max_dp[st][it]+max_dp[it+1][ed]);
                    min_dp[st][ed]=min(min_dp[st][ed],max_dp[st][it]+min_dp[it+1][ed]);
                }
			}

		}
	}
    

    
    return max_dp[0][nums.size()-1];
}

 

이번엔 조금 더 발전 된 문제를 풀어보자.

 

문제 링크3

https://www.acmicpc.net/problem/16639

16639번: 괄호 추가하기 3

문제 풀이

언뜻 이전의 문제에서 '*' 부분만 수정하면 될 것 같지만, 고려해야할 사항이 하나 있다.

A+B는 A,B 각각이 최대값일 때 최대값이 되지만, A*B 는 둘다 최댓값이라고 최댓값이 되지 않는다.

그 이유는 둘 중 하나, 혹은 둘 모두 '음수' 일 경우가 존재하기 때문이다.

 

따라서 * 부분의 dp를 계산할 때   max* max, max*min, min*max, min*min 4가지 경우의 수를 모두 구하고 그중 가장 큰값, 가장 작은 값을 dp에 할당해야한다.

 

정답 코드

#include<iostream>
#include<vector>
#include<math.h>
using namespace std;
int nums_len, ops_len;
long long max_dp[22][22];
long long min_dp[22][22];
int main() {
	int n;
	cin >> n;
	int num;
	char op;
	vector<int> nums;
	vector<char> ops;
	cin >> num;
	nums.push_back(num);
	for (int i = 1; i < n; i+=2) {
		cin >> op >> num;
		ops.push_back(op);
		nums.push_back(num);
	}
	//nums[a] ops[a] nums[a+1]

	for (int i = 0; i < nums.size(); i++) {
		for (int j = 0; j < nums.size(); j++) {
			max_dp[i][j] = -9876543;
			min_dp[i][j] = 9876543;
		}
	}
	for (int i = 0; i < nums.size(); i++) {
		max_dp[i][i] = nums[i];
		min_dp[i][i] = nums[i];
	}

	for (int len = 1; len < nums.size(); len++) {
		for (int st = 0; st+len < nums.size(); st++) {
			int ed = st + len;
			//cout << st << " " << ed << endl;
			
			for (int op_point = st; op_point < ed; op_point++) {
				if (ops[op_point] == '-') {
					max_dp[st][ed] = max(max_dp[st][ed], max_dp[st][op_point] - min_dp[op_point+1][ed]);
					min_dp[st][ed] = min(min_dp[st][ed], min_dp[st][op_point] - max_dp[op_point+1][ed]);
				}
				else if (ops[op_point] == '*') {
					//==========두 수의 곱이 최대가 되는 조건
					//양수 * 양수 == 양수   max*max
					//음수 * 음수 == 양수   min*min
					//양수 *음수 ==음수  ->  min*max
                    //음수*양수 ->  max, min
                    
                    //==========두 수의 곱이 최소가 되는 조건
					//양수 * 양수 == 양수   min*min
					//음수 * 음수 == 양수   max*max
					//양수 *음수 ==음수  ->  max*min
                    //음수*양수 ->  min, max
					
					long long max_p1 = max(max_dp[st][op_point] * max_dp[op_point + 1][ed], min_dp[st][op_point] * min_dp[op_point + 1][ed]);
					long long max_p2 = max(max_dp[st][op_point] * min_dp[op_point + 1][ed], min_dp[st][op_point] * max_dp[op_point + 1][ed]);
					max_dp[st][ed] = max(max_dp[st][ed],max(max_p1,max_p2) );

					long long min_p1 = min(max_dp[st][op_point] * max_dp[op_point + 1][ed], min_dp[st][op_point] * min_dp[op_point + 1][ed]);
					long long min_p2 = min(max_dp[st][op_point] * min_dp[op_point + 1][ed], min_dp[st][op_point] * max_dp[op_point + 1][ed]);

					min_dp[st][ed] = min(min_dp[st][ed], min(min_p1,min_p2));
				}
				else if (ops[op_point] == '+') {
					max_dp[st][ed] = max(max_dp[st][ed], max_dp[st][op_point] + max_dp[op_point+1][ed]);
					min_dp[st][ed] = min(min_dp[st][ed], min_dp[st][op_point] + min_dp[op_point+1][ed]);
				}

			}
			
		}
	}

	cout << max_dp[0][nums.size() - 1];


	

}