[C++] 11049번 행렬 곱셈 순서 - DP

#include <iostream>
#include <algorithm>

#define LOOP(i, N) for(int i=1; i<=N; i++)
#define MAX_N 501
#define INF 987654321

using namespace std;

int N;  //행렬의 개수
int arr[MAX_N+1][2];  //행렬의 크기
int dp[MAX_N+1][MAX_N+1];

void input()
{
    cin >> N;
    LOOP(i, N) cin >> arr[i][0] >> arr[i][1];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    input();
    
    for(int i=1; i<N; i++) {  //크기가 작은 행렬 곱
        for(int j=1; i+j<=N; j++) {
            dp[j][i+j] = INF;
            for(int k=j; k<=i+j; k++)  //두 부분으로 나누기
                dp[j][i+j] = min(dp[j][i+j], dp[j][k] + dp[k+1][i+j] + arr[j][0]*arr[k][1]*arr[i+j][1]);
        }
    }
    cout << dp[1][N];
    
    return 0;
}

<알고리즘>

두 개의 행렬을 행렬곱했을 때의 최솟값은 그냥 두 행렬을 곱한 것과 같다. 3개의 행렬을 행렬곱했을 때 최솟값은 2개의 행

렬과 1개의 행렬로 나눠서 구한 것중 최솟값이다.

 

즉 크기가 작은 개수의 행렬곱부터 구하면서 크기가 큰 행렬은 크기가 작은 두 행렬로 쪼개고 최솟값을 얻는 것이다.

 

 

분명히 코드의 방법은 똑같은 데 시간차가 많이 난다. cin이랑 scanf, cout랑 printf의 차이점 때문인 것 같다.

 

 

<scanf,printf 코드(풀어야 볼 수 있습니다.)>

https://www.acmicpc.net/source/8139503

로그인

 

 

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.