문제

11066번: 파일 합치기

풀이

이 문제는 파일끼리의 순서가 뒤섞이면 안된다. 항상 파일의 순서를 지켜 연속적인 두 파일만을 합칠 수 있다.

파일이 i번 ~ j-1번 까지의 파일을 모두 합치는데 비용을 dp[i][j]이라 한다면
점화식 dp[i][j] = min(dp[i][k] + dp[k][j]) + sum(i~j-1)을 이용해서 구할 수 있다.

• k의 범위 : i+1 <= k < j
• sum(i ~ j-1) : i부터 j-1까지의 누적합, 누적합 배열을 통해 prefix(j) - prefix(i)로 구할 수 있다.
• dp[i][i] = 0 , dp[i][i+1] = prefix(i+1) - prefix(i)로 초기값을 설정한다.
  • dp[i][i]: 사실상 k값을 잘 조절한다면 참조할 일이 없다.
  • dp[i][i+1]: 파일 하나를 합치는것은 불가능하지만 최소 비용으로 설정된다.
    
    

재귀 함수
위의 점화식을 이용해서 다이나믹 프로그래밍으로 문제를 해결할 수 있다.
dp(i, j) = min(dp(i, k) + dp(k, j) + prefix[j] - prefix[i])를 통함 재귀호출로
dp(0, n)의 리턴값을 출력하면 된다.
이때 모이제이션을 위한 2차원 배열을 사용하여 불필요한 중복 값을 줄인다.

재귀 함수를 사용하면 점화식을 직관적으로 사용할 수 있다는 장점이 있지만 함수를 호출하는데에 시간이 걸린다. 좀 더 빠른 방법을 원한다면 재귀함수 호출이 아닌 3중 반복문으로도 해결할 수 있다.

반복문
2차원 배열을 순회하며 최정적으로 dp[0][n]의 위치에 알맞은 값을 넣어야 하는데 그 순서를 바로 알기 어려웠다.

대각선 방향으로 탐색을 하며 자신의 인덱스에 맞는 값을 구하면 된다.
값을 구하기 위해 k는 left+1 <= k < right를 탐색하기에 3중 for문이 된다.

더 빠른 방법을 위해 Knuth Optimization을 사용하는 풀이도 있지만 아직 이해하지 못했다.

코드

재귀 함수

#include <iostream>
#include <vector>

using namespace std;

vector<int> arr;
vector<vector<int>> memo;
vector<int> prefix;

int min(int a, int b) { return a < b ? a : b; }

int dp(int a, int b)
{
    if (memo[a][b] != INT32_MAX)
        return memo[a][b];
    
    if ( b-a == 1) 
        return memo[a][b] = 0;
    else if (b-a == 2)
        return memo[a][b] = prefix[b] - prefix[a];

    int minVal = INT32_MAX;

    for (int i=a+1; i<b; ++i)
    {
        int dpA = dp(a, i);
        int dpB = dp(i, b);

        minVal = min( minVal, dpA + dpB + prefix[b] - prefix[a]);
    }

    return memo[a][b] = minVal;
}

int main() 
{
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    int testcase;
    cin >> testcase;
    while (testcase--)
    {
        int n;
        cin >> n;

        arr.resize(n);
        memo.assign(n+1, vector<int>(n+1, INT32_MAX));
        prefix.assign(n+1, 0);

        for (int i=0; i<n; ++i)
            cin >> arr[i];
        
        for (int i=0; i<n; ++i)
            prefix[i+1] = prefix[i] + arr[i];

        int answer = dp(0, n);
        
        cout << answer << "\n";

        arr.clear();
        memo.clear();
        prefix.clear();
    }
    return 0;
}

for 반복문

#include <iostream>
#include <vector>

using namespace std;


int min(int a, int b) { return a < b ? a : b; }

int main() 
{
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    int testcase;
    cin >> testcase;
    while (testcase--)
    {
        int n;
        cin >> n;

        vector<int> arr(n);
        vector<int> prefix(n+1, 0);
        vector<vector<int>> dp (n+1, vector<int>(n+1, 0));

        for (int i=0; i<n; ++i)
            cin >> arr[i];
        
        for (int i=0; i<n; ++i)
            prefix[i+1] = prefix[i] + arr[i];


        for (int i=2; i<n+1; i++) // 파일 간격
        {
            for (int j=0; i+j<n+1; ++j) // 반복할 파일 시작번호
            {
                int left = j;
                int right = i+j;
                int minVal = INT32_MAX;
                for (int mid = left+1; mid < right; ++mid)
                {
                    minVal = min(minVal, dp[left][mid] + dp[mid][right] + prefix[right] - prefix[left]);
                }
                dp[left][right] = minVal;
            }
        }
        cout << dp[0][n] << "\n";
    }
    return 0;
}