[백준/BOJ] 11066번 : 파일 합치기, 11049번 : 행렬 곱셈 순서 (DP, 동적 계획법 중급)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 11066번 : '파일 합치기', 11049번 : '행렬 곱셈 순서' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제 난이도는 Solved.ac 기준 Gold 티어에 해당하며, 문제를 풀이하기 위해 DP(동적 계획법)의 활용에 대한 이해가 필요합니다.

 

 

11066번 : 파일 합치기

 

파일을 합칠 때 인접한 두 덩어리를 합치는 비용은 두 덩어리의 파일 크기의 합일 때, 모든 파일을 하나로 합치도록 하는 최소 비용을 구하는 문제입니다.

당연하겠지만 입력 값들의 크기는 무작위로 주어질 수 있기 때문에 DP를 활용하여 배열에 모든 경우의 수를 기록해나가면서 연산 시간을 감소시키는 방법이 가장 무난한 풀이입니다.

 

따라서 cost[a][b]를 a 페이지부터 b 페이지까지 취합하는데에 필요한 최소 비용이라고 정의하고 문제를 풀이하면 비교적 쉽게 해결이 가능합니다.

cost[1][2] → cost[2][3] → ... → cost[N-1][N]까지 먼저 기록하고, 그 다음에 cost[1][3] → cost[2][4] → cost[N-2][N]을 기록하는 식으로 해서 DP에 최소 비용을 찾아 계산해주면 됩니다.

물론 그 과정에서 cost[i][i+j] = min(cost[i][i+j], cost[i][k] + cost[k+1][i+j]) + sum[i+j] - sum[i-1] 이라는 점화식을 세워 k에 대한 반복문이 한 번 더 들어가야 j 크기의 구간에서 최솟값을 성공적으로 찾아줄 수 있습니다.

뒤에 sum[i+j] - sum[i-1]을 더해주는 이유는 i ~ j 구간의 각 페이지들만큼 비용이 추가로 들어가기 때문입니다.

 

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int T; cin >> T;

    while(T--) {
        int N; cin >> N;

        vector<int> sum(N+1);
        for(int i=1; i<=N; i++) {
            int value; cin >> value;
            sum[i] = sum[i-1] + value;
        }

        vector<vector<int>> cost(N+1, vector<int>(N+1));
        for(int j=1; j<=N; j++)
            for(int i=1; i<=N-j; i++) {
                cost[i][i+j] = INT_MAX;
                for(int k=i; k<i+j; k++)
                    cost[i][i+j] = min(cost[i][i+j], cost[i][k] + cost[k+1][i+j]);
                cost[i][i+j] += sum[i+j] - sum[i-1];
            }

        cout << cost[1][N] << "\n";
    }
}

 

설명을 풀이 코드로 옮겨적으면 위와 같이 됩니다.

최종적으로 구하는 답은 1 ~ N 페이지를 취합할 때 필요한 최소 비용이므로 당연히 cost[1][N]을 출력해주면 됩니다.

메모리를 상대적으로 아끼기 위해 이중 벡터를 위와 같이 선언하여 크기를 N+1 × N+1로 잡아주었습니다.

 

 

 

 

11049번 : 행렬 곱셈 순서

 

N개의 행렬을 곱할 때 최소 연산 수를 구하는 문제입니다.

이 문제 역시 위의 문제와 마찬가지로 하나의 공식으로 해결하기 복잡하므로 DP에 하위 단계의 연산의 수들을 기록하여 가장 적은 연산의 수를 구하는 방식을 사용하는 편이 편합니다.

 

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;

    vector<int> row(N+1), col(N+1);
    for(int i=1; i<=N; i++)
        cin >> row[i] >> col[i];

    vector<vector<int>> dp(N+2, vector<int>(N+2));
    for(int i=N; i>0; i--)
        for(int j=i+1; j<=N; j++) {
            dp[i][j] = INT_MAX;
            for(int k=i; k<j; k++)
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + row[i] * col[k] * col[j]);
        }

    cout << dp[1][N];
}

 

풀이 역시 비슷한데, dp[i][j]를 i번째 행렬부터 j번째 행렬까지를 곱하는데 필요한 최소 연산 횟수로 정의합니다.

뒤쪽부터 계산하면서 최소 연산 횟수를 기록해주는 방식을 사용합니다.

그러니까 dp[N-1][N] → dp[N-2][N-1] → dp[N-2][N] → dp[N-3][N-2] → dp[N-3][N-1] → dp[N-3][N]  → ...와 같은 순서로 값들을 기록해나가면 최소 연산 횟수를 빠짐없이 기록할 수 있습니다.

 

그리고 dp[i][j]는 dp[i][j]와 dp[i][k] + dp[k+1][j]에 k번째 행렬과 k+1번째 행렬을 곱하는데 필요한 연산의 수를 더한 값 중 더 작은 값을 선택해주면 됩니다.

k번째 행렬과 k+1번째 행렬을 곱하는데 필요한 연산 횟수는 i번째 행렬의 행의 수 * k번째 행렬의 열의 수(= k+1번째 행렬의 행의 수) * j번째 행렬의 열의 수로 나타낼 수 있습니다. (이것은 행렬의 기본적인 곱의 성질입니다.)

 

 

 

다시 보니까 제가 4천만번째 제출이 될 수 있었는데 아쉽네요.

아무튼 풀이 코드를 작성하여 제출하면 위와 같은 기록으로 통과할 수 있습니다.