[백준/C++] 11049번 행렬 곱셈 순서

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

11049번: 행렬 곱셈 순서

알고리즘 수업에 나온 내용이 백준 문제에 있길래 풀어보았다.

우선 행과 열 값들을 저장해준다.

그런 다음 삼중 for문(O(n^3)) 을 이용해 값을 구해준다. 행렬곱셈의 순서는 다른 dp 문제들과 동일하다.

바텀 업으로 시작하여 값을 계산하고, 계산된 값을 저장한다. 그리고 그 계산된 값을 이용하여 답을 구하는 것이다.

행렬 곱셈순서를 구하기 위해서는 몇개를 곱할 것인지, 시작점은 어디인지, 기준점은 무엇인지 총 3개의 큰 부분으로 나눌 수 있다.

구간의 크기는 최소 1부터 최대 n-1까지 진행하며 (당연히 구간의 크기가 n이 될 순 없다)

시작점은 최소 1부터 최대 i+j <= n인데, 이것은 열 값을 i+j로 표현하기 때문에 그렇다.

기준점은 j부터이며 현재 열 값(i+j)보다 작아야 한다. 기준점은 당연히 시작점보다 크거나 같아야하므로 j부터 시작한다.

!! 왜 열 값을 i+j로 하냐? -> 행렬의 곱셈은 증가한다 -> 열이 행보다 항상 커야한다 -> A1 * A2 * ... * A7 이런 식으로 가는 것이 문제의 조건이기 때문에, N by N 배열에서 대각선과 그 밑은 사용하지 않는 것! 

또한 matrix[j][0] 은 구간 시작 부분의 행렬의 행 (N 역할), matrix[k][1] : 구간을 둘로 나누는 기준점 행렬의 열 (M 역할), matrix[i+j][1] : 구간 마지막 부분의 행렬의 열 (K 역할) 이다.

ex) dp[2][3] = min(dp[2][3], dp[2][3] + dp[3][4] + N * M * K);

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

int n,r,c;
int dp[501][501];
int matrix[501][2];

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

    cin >> n;

    for(int i=1; i<=n;i++){
        cin >> r >> c;
        matrix[i][0]=r;
        matrix[i][1]=c;
    }
    for (int i = 1; i < n; i++)// 구간의 크기 = 곱하는 행렬의 수
    {
        for (int j = 1; i + j <= n; j++) // 시작점
        {
            dp[j][i + j] = 987654321; // 초기화
            for (int k = j; k <= i + j; k++) // k는 기준점
            {
                dp[j][i + j] = min(dp[j][i + j], dp[j][k] + dp[k + 1][i + j]
                + matrix[j][0] * matrix[k][1] * matrix[i+j][1]);
            }
        }
    }
    cout << dp[1][n];
    return 0;
}