백준 11049번 : 행렬 곱셈 순서

  처음 문제 읽고 든 생각이 '아 이거 왠지 수학적 지식이 있거나 조금 더 연구를 해보면 완전 아름다운 코드를 짤 수 있을 것 같아!'였다. 하지만 그런걸 생각하기 귀찮으니 그냥 정석적인 DP로 풀도록 하자...ㅎㅎ

 

  기본적인 풀이 방법은 이렇다.

---

a번째 행렬부터 b번째 행렬까지 곱하는데 필요한 최소 계산 횟수를 calCnt[a][b]라고 하자.

a번째 행렬부터 b번째 행렬까지 어떻게 곱할것이냐면!

a번째부터 k번째까지 곱한 행렬에다가 k+1번째부터 b번째까지 곱한 행렬을 곱할 것이다.

 

calCnt[a][b] = calCnt[a][k] + calCnt[k+1][b] + 두 행렬을 곱하는데 필요한 계산 횟수

두 행렬을 곱하는데 필요한 계산 횟수 = a번째 행렬의 행 개수 * k번째 행렬의 열 개수 * b 번째 행렬의 열 개수

이 때 k는 a<= k < b이므로 for문을 한 번 돌려준다! 물론 기존의 DP처럼 그 결과값을 다른 곳에 저장해둬서 동일한 계산이 반복되지 않도록 하자.

 

#include <iostream>

using namespace std;

int MAX = 2147483647;
int n;
int mat[502][2];
int calCnt[502][502];

int matCnt(int a, int b)
{
    if(a == b) return 0;
    if(calCnt[a][b] != 0) return calCnt[a][b];
    
    calCnt[a][b] = MAX;
    for(int i = a; i < b; i++)
    {
        calCnt[a][b] = min(calCnt[a][b], matCnt(a, i) + matCnt(i+1, b) + mat[a][0] * mat[i][1] * mat[b][1]);
    }
    
    return calCnt[a][b];
}

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> mat[i][0] >> mat[i][1];
    }
    
    cout << matCnt(0, n-1);
 
    return 0;
}