정리충의 정리노트

[백준] 11049: 행렬 곱셈 순서 본문

PS/DP

[백준] 11049: 행렬 곱셈 순서

ioqoo 2020. 1. 23. 19:29

0. 문제 주소

 

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

 

11049번: 행렬 곱셈 순서

첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같다.

www.acmicpc.net

 

 

1. 풀이

 

2차원 배열을 이용하여 모든 구간별 정보를 메모이제이션 하는 dp 문제.

 

다시 말해서, i번째 행렬부터 j번째 행렬까지 곱했을 때의 최소 곱셈 횟수를 저장할 것이기 때문에, 이 정보들을 이용하기 위해선 곱셈 형태를 큰 부분 두 개로 나누어야 한다.

 

A, B, C, D 4개의 행렬이 있다고 가정해 보자.

메모이제이션을 통해 A ~ C , 그리고 B ~ D 를 곱할 때의 최소 곱셈 횟수를 기억해뒀다고 가정하면, 가능한 경우는

 

1. (A B C) x D ----> A B C의 최소 곱셈 횟수 + D의 최소 곱셈 횟수 (= 0) + ABC x D에서 발생하는 곱셈 횟수

2. (A B) x (C D) ----> A B의 최소 곱셈 횟수 + C D의 최소 곱셈 횟수 + AB x CD에서 발생하는 곱셈 횟수

3. A x (B C D) ----> A의 최소 곱셈 횟수 (= 0) + B C D의 최소 곱셈 횟수 + A x BCD에서 발생하는 곱셈 횟수

 

라고 정리할 수 있다.

 

참고로 여기서 dp[i][j] 는 i번째 행렬부터 j번째 행렬까지 곱했을 때의 최소 곱셈 횟수를 저장하기 때문에,

i <= j를 만족하게 되고, 따라서 dp 테이블은 upper triangular의 형태를 갖게 된다.

 

 

i == j일 때는 행렬이 하나일 때이므로, 별다른 횟수가 필요없다. 즉 dp[i][j] == 0 (i == j)

 

i == j-1일 때는, 바로 인접한 행렬 두 개를 곱할 때이므로,

가능한 곱셈 방법은 한 가지고 바로 그 때의 횟수가 최소 곱셈 횟수가 된다. 

 

이렇게 두 가지의 초기 케이스를 초기화 해주고, 아래 코드와 같이 dp 테이블을 채워준 후, dp[1][N]에 저장된 값을 출력하면 된다.

 

 

2. 풀이 코드

 

* 유의할 점

1. 중간 과정에서 혹시 발생할지도 모를 오버플로우에 대비하여 long long 자료형 사용

2. mat 배열은 pair<long long, long long> 자료형 이용, first에는 row, second에는 column값 저장

3. 대각 성분, 그리고 그 바로 위 성분은 미리 초기화.

 

#include <bits/stdc++.h>
#define MAX 505
#define ll long long
#define pll pair<ll, ll>
#define INF 1e11

using namespace std;

int N;
pll mat[MAX]; // first : row, second : column
ll dp[MAX][MAX];


int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    #endif // ONLINE_JUDGE

    scanf("%d", &N);
    for (int i=1;i<=N;i++){
        ll r, c;
        scanf("%lld %lld", &r, &c);
        mat[i] = pll(r, c);
    }
    for (int i=1;i<N;i++){
        dp[i][i+1] = mat[i].first * mat[i].second * mat[i+1].second;
    }
    for (int d=2;d<=N-1;d++){
        for (int i=1;i<=N-d;i++){
            ll curr_min = INF;
            int j = i + d;
            for (int k=i;k<j;k++){
                curr_min = min(curr_min, mat[i].first * mat[k].second * mat[j].second + dp[i][k] + dp[k+1][j]);
            }
            dp[i][i+d] = curr_min;
        }
    }

    printf("%lld\n", dp[1][N]);
}

 

 

 

'PS > DP' 카테고리의 다른 글

[백준] 2533: 사회망 서비스  (0) 2020.01.24
[백준] 11066: 파일 합치기  (0) 2020.01.24
[백준] 9084: 동전  (1) 2020.01.20
[백준] 9251: LCS  (0) 2020.01.19
[백준] 2169: 로봇 조종하기  (0) 2020.01.19
Comments