백준 11049 행렬 곱셈 순서

어제에 이어 오늘도 DP 접근 문제이다. 이 문제도 학교 알분시간에 한번 다뤘었던 기억이 나는데 꼭 항상 학교에서 한것은 했다는 그 사실만 기억나고 내용은 기억이 나지 않는다... 하하하...

DP 문제에서 관건은 문제가 쪼개지는지, 그 문제들의 합이 전체 해가 되는지인것같다. 만약 이 조건이 만족한다면 DP적 접근을 해보는게 좋을 것 같다.

 

해당 문제는 어떤 특정 부분의 최소값이 전체 최소값의 부분을 차지한다. 따라서 DP적 접근을 하는게 좋아보인다.

DP 배열은 dp[i][j]일때, i번째 행렬부터 j번째 행렬까지 곱의 최소횟수를 의미한다. 처음 초기화는 전부 0으로 하고, 이웃한 배열끼리의 곱은 무조건 고정되어있으므로, 0~N-1 배열까지 이웃한 값을 채워줄 수 있다.

 

이후로는 저번 문제들과는 다르게 한행한행 채우는것이 아니라, i로부터 차이를 늘려가며 채우게 된다. 이웃한 행렬은 이미 채워져 있고, d를 2부터 N까지 늘려가며 채운다. 처음엔 d = 2 므로, i부터 j = i + 2까지  k를 사용해 탐색해가며 곱의 최소값을 찾게 된다.

만약 d가 좀 커진 수(ex. 5)라고 가정하자. i부터 j = i + 5 까지 k를 사용해 무엇을 탐색하냐면, 해당 행렬들의 곱을 어떻게 나누어 계산할것인지를 찾는다. 처음엔 첫번째 행렬 * 나머지 애들의 곱 으로 횟수를 계산하고, 다음엔 (1, 2 번째 행렬) * (3, 4, 5 번째 행렬) ... 이렇게 횟수를 계산해서 최소값을 찾아 dp[i][j]에 넣게 된다.

행렬의 연산횟수는 dp[i][k] + dp[k + 1][j] + mat[i].first * mat[k].second * mat[j].second 가 된다.

i 부터 k 까지 연산횟수 + (k + 1)부터 j까지 연산횟수 + 두 행렬의 곱 횟수 로 이해하면 된다.

 

그렇게 dp를 채우고, dp[0][N-1] 을 구하면 딱 0번째(첫번째 행렬) 에서부터 N-1번째(마지막 행렬)까지 곱하기 횟수의 최소값을 구할 수 있다.

---

#include <iostream>
#include <vector>

int main()
{
    int N;
    std::cin >> N;
    std::vector<std::pair<int, int> > matrixList;
    for (int i = 0; i < N; ++i)
    {
        int M, K;
        std::cin >> M >> K;
        matrixList.push_back(std::make_pair(M, K));
    }
    std::vector<std::vector<long long> > dp(N, std::vector<long long>(N, 0));
    // dp[i][j] = i 번째부터 j 번째 행렬까지 곱의 최소 연산개수.
    // 인접한 행렬
    for (int i = 0; i < N - 1; ++i)
    {
        dp[i][i+1] = matrixList[i].first * matrixList[i].second * matrixList[i+1].second;
    }
    // i에서의 차이가 2 이상인 것부터 채워나가기 -> 1인건 인접행렬임.
    for (int d = 2; d <= N ; ++d)
    {
        for (int i = 0; i < N - d; ++i)
        {
            int j = i + d;
            for (int k = i ; k < j; ++k) // i부터 j까지 중, i~k 까지 행렬 곱 * k+1~j까지 행렬 곱 하는 횟수
            {
                long long kCnt = dp[i][k] + dp[k+1][j] + matrixList[i].first * matrixList[k].second * matrixList[j].second;
                if (!dp[i][j] || dp[i][j] > kCnt)
                    dp[i][j] = kCnt;
            }
        }
    }
    std::cout << dp[0][N - 1];
}

DP는 참 보면 볼수록 어려운데 매력적인것 같다. 복잡해보이는 문제도 루프몇개에 배열채우기만 하고, 마지막에 한 값만 찾아다가 구하면 답이고... 수학적 생각이 중요한 접근 방식인듯 하다. 아 초중딩때 문제푸는 방법찾기 단원이 제일 빡셌는데 딱 그거 푸는 느낌이다. 허허허...

이말은 꾸준히 하는것 같은데, 정말 꾸준히 봐야겠다...

 

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