파일 합치기 11066

문제

접근 방법

	40	30	30	50
40	0
30		0
30			0
50				0

예제로 표를 만들었다.

	40	30	30	50
40	0	70
30		0	60
30			0	80
50				0

2개씩 짝지으면 이럴 것이다. 40, 50의 경우는 고려하지 않는다. (연속되도록 합쳐나간다는 부분이 있으므로 누적 합을 이용하면 된다)

	40	30	30	50
40	0	70	170, 160
30		0	60	170 ,190
30			0	80
50				0

둘 중 최솟값을 사용할 것이다.

	40	30	30	50
40	0	70	160	300, 310, 320
30		0	60	170
30			0	80
50				0

300으로 결론이 난다.
예시를 보면 알듯이 한 단계를 올라갈수록 최솟값으로 고려할 수 있는 경우가 늘어나며 (2개의 범위일 때는 1개, 3개의 범위일 때는 2개, 4개의 범위일 때는 3개, N개의 범위일 때는 N-1개) 해당 범위에서의 누적된 비용은 동일하다. (최종답에 해당하는 300, 310, 320은 누적된 비용인 150(40+30+30+50)에 (70+80), 160, 170을 한 형태이다)
해당하는 내용을 이용하면 코드를 작성할 수 있다.

코드

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int dp[501][501];
int prefix[502];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int T;
    cin >> T;
    while (T--)
    {
        int K;
        cin >> K;
        memset(dp, 0x3f, sizeof(dp));
        for (int i = 0; i < K; ++i)
        {
            int n;
            cin >> n;
            prefix[i + 1] = n;
            dp[i][i] = 0;
        }
        for (int i = 2; i <= K; ++i)
        {
            prefix[i] += prefix[i - 1];
        }
        for (int i = 1; i < K; ++i) // 범위
        {
            for (int j = 0; j < K - i; ++j) // 시작점
            {
                int preSum = prefix[j + i + 1] - prefix[j];
                for (int k = 0; k < i; ++k) // 범위 안에서의 여러 선택
                {
                    dp[j][j + i] = min(dp[j][j + i], dp[j][j + k] + dp[j + k + 1][j + i]);
                }
                dp[j][j + i] += preSum;
            }
        }
        cout << dp[0][K - 1] << "\n";
    }
    return 0;
}

풀이

반복문에 활용되는 변수가 늘어나면 헷갈린다.
파일을 어떤 순서로 합치느냐에 따라 값이 달라진다는 점을 생각하여 반복문을 작성하면 된다.