백준 11066 파일 합치기

오랜만이다. 역시 DP 문제이다. 처음 접근했을때는 어 이거 저번에 풀었던 행렬 곱셈 순서랑 너무 비슷한데? 해서 최대한 풀이를 보지 않고 접근해보았다.

일단 dp[i][j] 배열은, i번째 장에서부터 j번째 장 까지 합친 비용의 최소값이다. 추가로, sum[i] : 0 ~ i번째 원소까지 누적합을 저장하는 배열도 선언해준다.

 

그럼 이제 몇개의 예시를 돌려보자.

dp[i][i] = sum[i] - sum[i - 1]

dp[i][i+1] = sum[i + 1] - sum[i - 1]

dp[i][i+2] = min(dp[i][i] + dp[i+1][i+2], dp[i][i+1] + dp[i+2][i+2]).

 

만약 1~10 장의 합치는 개수를 구하고 싶으면(dp[1][10]), dp[1][1] + dp[2][10] , dp[1][2] + dp[3][10] ... 을 전부 돌려보며 dp 배열 셀에 들어갈 최소값을 찾으면 된다.

그러기 위해서는 일단 각 페이지와 이웃한 값부터 하나씩 거리를 늘려가며 채운다(코드에서 d) 그러고, k(탐색 중간값) 을 하나씩 늘리며 셀의 최소값을 구한다.

합치는 연산의 비용은 합쳤을때 페이지의 합이라 했으므로, 각 dp에 저장되어 있던 연산횟수를 더해줄때 이번 합치는 연산도 더해준다(sum[j] - sum[i - 1])

 

그렇게 전부 루프를 돌며 dp를 채우고, dp[1][N] 을 출력하면, 첫번째 장부터 마지막 장 까지 합치는 연산의 최소값을 구할 수 있다!

---

#include <iostream>
#include <vector>
#include <cstring>

int main()
{
    int T;
    std::cin >> T;
    while (T--)
    {
        int N;
        std::cin >> N;
        int CList[N + 1];
        int sum[N + 1];
        memset(CList, 0, sizeof(CList));
        memset(sum, 0, sizeof(sum));
        for (int i = 1; i <= N; i++)
        {
            std::cin >> CList[i];
            if (i == 0)
                sum[i] = CList[i];
            else
                sum[i] = sum[i - 1] + CList[i];
        }
        std::vector<std::vector<long long> > dp(N + 1, std::vector<long long> (N + 1, 0));

        //인접한애들
        // for(int i = 0; i < N - 1; ++i)
        // {
        //     dp[i][i+1] = CList[i] + CList[i+1];
        //     dp[i][i] = CList[i];
        // } 그냥 루프에서 다 처리
        for (int d = 1; d <= N; ++d)
        {
            for (int i = 1; i <= N - d; ++i)
            {
                int j = i + d;
                for (int k = i; k < j; ++k)
                {
                    // dp[4][11] = min(dp[4][11], dp[4][5] + dp[6][11] + sum[11] - sum[3]) i:4, j:11, k:5
                    //  sum[11] - sum[3] 은 해당 범위 연산 합. -> 그 범위를 합치면 무조건 해당 cost가 발생하므로 더해주나보다.
                    long long kCnt = dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1];
                    if (!dp[i][j] || dp[i][j] > kCnt)
                        dp[i][j] = kCnt;
                }
            }
        }
        std::cout << dp[1][N] << '\n';
    }
}
//https://cocoon1787.tistory.com/317
//https://kyunstudio.tistory.com/75
//http://melonicedlatte.com/algorithm/2018/03/22/051337.html

포스팅을 좀 쉬었더니 어렵다. 다시 꾸준히 해보자~

역시 문제를 풀고 마는것보다 한번 글로 써보면서 정리하는게 이해가 잘 되는 것 같다. 이번 문제에서 kCnt를 구하는 식도 왜 마지막에 sum 배열에서 두개를 더하고 빼지? 했는데 글 작성하면서 이해가 잘 된것 같다.

 

오늘도 평온한 하루가 되길. 슨민.