[백준/Baekjoon] 11066 파일 합치기 C++ :: Dynamic Programming

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

11066번: 파일 합치기

---

1. Logic

DP를 푸는 방법은 늘 그렇듯 부분문제를 쪼개는게 핵심이다.

 

이 문제에서 부분문제를 생각해보면 파일을 어떻게 나눌건지를 생각해야된다.

 

문제에서 나온 테스트케이스를 보면

40 30 30 50이다. 여기서 파일의 순서를 임의로 바꿀 수 없는것을 유의하면 부분문제는 총 3가지로 볼 수 있다.

나누는 부분을 보면 아래와 같다.

40 / 30 30 50

40 30 / 30 50

40 30 30 / 50 

 

답에서 나온 예제의 최적은 40-30 + 30-50을 더한 후 두개를 더하는방식이 최적이다.이를 재귀적으로 생각해보면 

처음 함수에 0~n-1의 범위를 가지고 들어갔다가 40-30이 묶이는 idx 1에서 재귀를 호출한다. 이 부분은 아래의 코드를 보고 디버깅 해보면 나올 것이다.

 

즉 DP배열이 의미하는 것은 idx와 idx사이에 있는 파일을 더했을 때 나올 수 있는 합의 최솟값이다.

---

2. Code

#include<bits/stdc++.h>

using namespace std;

int dp[501][501];
int psum[501];
int input[501];

int n;

int solve(int left, int right) {
    if(left == right) return 0;
    
    int &ret = dp[left][right];
    if(ret != -1) return ret;
    ret = 0x3f3f3f3f;
    
    for(int i = left; i < right; i++) {
        int temp = solve(left, i) + solve(i+1, right);
        //파일 각자의 용량만 더해줌
        temp += psum[i] - (left > 0 ? psum[left-1] : 0); //쪼개진 부분에서 왼쪽 구하기
        temp += psum[right] - psum[i]; //쪼개진 부분에서 오른쪽 구하기
        
        ret = min(ret, temp);
    }
    
    return ret;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	int t;
	cin >> t;
	
	while(t--) {
	    memset(dp, -1, sizeof(dp));
	    memset(input, 0, sizeof(input));
	    
	    cin >> n;
	    
	    for(int i = 0; i < n; i++) {
	        cin >> input[i];
	        psum[i] = input[i];
	        if(i > 0) psum[i] += psum[i-1];
	    }
	    cout << solve(0, n-1) << '\n';
	}
}

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐