(백준/ C++) 11066 - 파일합치기 [너무 어려웠던 ..멘탈 탈탈]

11066번: 파일 합치기 (acmicpc.net)

11066번: 파일 합치기

 

너무 어려웠던 .. 파일 합치기 .. 많은 블로거들이 포스팅한 글을 봐도 이해가 거의 안갔다 @_@.. ㅋㅋㅋ

억지로 외우고 따라 써보고 코드 그대로 그림을 그려보니 이해가 갔던 문제 였습니다.. 

다시 보고 또 다시 봐야 할 거 같습니다.

<hide/>
	for(int idx = 1; idx < K ; ++idx) {
            for(int x = 1; x + idx <= K; ++x)
            {
                int y = x + idx; 
                dp[x][y] = 1000'000'007;
                for(int mid = x; mid < y; ++mid)
                {
                    dp[x][y] = 
                    min(dp[x][y], dp[x][mid]+dp[mid+1][y]+sum[y]-sum[x-1]);  
                }
            }
        }

자 이걸 하나하나씩 뜯어보면서 이해해봅시다..

40 30 30 50 으로 예시를 들어봅시다.

누적 합 공식으로 만들어진 테이블

* DP[i][j]: i~j까지의 최소합을 담을 테이블

즉, 우리의 목적은 DP[1][K]의 값을 찾는 것입니다.

        for(int idx = 1; idx < K ; ++idx) {
            for(int x = 1; x + idx <= K; ++x) {
            	int y = x + idx; 
                for(int mid = x; mid < y; ++mid) {             
                }
            }
        }

이 위의 삼중코드에 K = 4를 대입하면 x, y는 아래와 같은 상황들이 만들어집니다.

 

 

 

 

 

 

이제 그 안에 있는 코드에 idx = 1인 상황부터 3인 상황까지 대입하게 되면

 dp[x][y] = min(dp[x][y], dp[x][mid]+dp[mid+1][y]+sum[y]-sum[x-1]);

Idx = 1 인 경우 

Idx = 2 인 경우

 Idx = 3 인 경우

상황이 나옵니다. 

혹시 저와 같이 sum[y] - sum[x-1] 대체 왜 하는거야? 라고 생각하시는 분들이 있을까봐 설명해드리겠습니다.

이유는 간단합니다. 문제에서 그렇게 요구했기 때문입니다! 

저는 예시는 x: 1, y: 3인 경우로 들겠습니다. 

■ + ■ + ■

여기서 빨간색은 어떻게 더하든 누적합이기 때문입니다!! 

당연한거아니야 ? 하는 사람도 있겠지만!! 저는 오랫동안 생각했다는것!! ^^ 그런 사람도 있습니다 .. 있다고요 .. 

오늘은 이 문제로 멘탈 탈탈 털린 날이였습니다 그럼 이만 ... 

#include <iostream>
using namespace std; 
#define MAX 501 
// 두 개의 파일을 합칠 때 필요한 비용이 두 파일 크기의 합
// 

    int testcase; 
    int arr[MAX];
    int sum[MAX]; 
    int dp[MAX][MAX]; 
int main(void)
{
    ios_base::sync_with_stdio(false); 
    cin.tie(0); 
    cout.tie(0);



    cin >> testcase; 

    while(testcase--)
    {
        int K; 
        cin >> K; 
        
        for(int i=1; i<=K; ++i) {
            cin >> arr[i]; 
            sum[i] = arr[i]+sum[i-1]; 
        }

        for(int idx = 1; idx <K ; ++idx) {
            for(int x = 1; x + idx <= K; ++x)
            {
                int y = x + idx; 
                dp[x][y] = 2'147'483'600;
                for(int mid = x; mid < y; ++mid)
                {
                    dp[x][y] = 
                    min(dp[x][y], dp[x][mid]+dp[mid+1][y]+sum[y]-sum[x-1]);  
                }
            }
        }
        
    cout << dp[1][K] << "\n";
    }

    
    
    return 0;
}