[백준/C++] #11049 행렬 곱셈 순서 (DP)

문제

https://www.acmicpc.net/problem/11049

 

 

구상

행렬 곱셈 연산의 수의 최솟값을 구하는 문제였다. 해당 문제가 11066번(https://persi0815.tistory.com/47)과 같이 작은 부분을 통해 큰 부분의 값을 알아낼 수 있었다. 처음에 착각했던게, a b c d라는 배열이 있으면, abc * d와 a* bcd의 연산만 가능하다고 생각했었다. 사실 ab*cd도 되는데.. 그래서 해당 부분 수정해서 로직을 짰더니 성공 !!

알고리즘

이전에 구한 값으로 다음 값을 구하니 dp 유형이다. 

 

풀이 + 코드

dp[i][j]는 행렬 i부터 행렬 j까지의 최소 행렬 곱셈 연산 수이다. 

최악의 연산수도 범위가 2^31-1보다 작다고 해서 int를 사용했다. 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#define INF 987654321
#define endl "\n"
using namespace std;
/*
11049 행렬 곱셈
*/                                                   

int main() {
    int N;

    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    // 입력
    cin >> N; // 1~500
    vector<pair<int, int>> vp(N); // 행렬 크기
    vector<vector<int>> dp(N, vector<int>(N, INF)); // dp[i][j]: i~j 행렬 연산의 최솟값

    // 행렬 크기 입력 
    for (int i = 0; i < N; i++) {
        cin >> vp[i].first >> vp[i].second;
    }

    // 행렬 연산의 최솟값 초기화
    for (int i = 0; i < N; i++) {
            dp[i][i] = 0;
    }

    // dp 연산
    for (int length = 2; length <= N; length++) { // 길이
        for (int s = 0; s <= N-length; s++) { // 시작점
            int e = s + length - 1; // 끝점
            for (int k = s; k < e; k++) { // 분할 지점
                dp[s][e] = min(dp[s][e], dp[s][k] + dp[k+1][e] + vp[s].first * vp[k].second * vp[e].second);
                //cout << k <<" " << dp[s][k] << " " << dp[k+1][e] << " " << vp[s].first * vp[k].second * vp[e].second << " dp[" << s << "][" << e << "]: " << dp[s][e] << endl;
            }
        }
    }
    
    cout << dp[0][N - 1];

    return 0;

}

 

 

해당 반례에 무한한 영광을..