(백준 c++)11049 행렬 곱셈 순서

문제

크기가 N×M인 행렬 A와 M×K인 B를 곱할 때 필요한 곱셈 연산의 수는 총 N×M×K번이다. 행렬 N개를 곱하는데 필요한 곱셈 연산의 수는 행렬을 곱하는 순서에 따라 달라지게 된다.

예를 들어, A의 크기가 5×3이고, B의 크기가 3×2, C의 크기가 2×6인 경우에 행렬의 곱 ABC를 구하는 경우를 생각해보자.

• AB를 먼저 곱하고 C를 곱하는 경우 (AB)C에 필요한 곱셈 연산의 수는 5×3×2 + 5×2×6 = 30 + 60 = 90번이다.
• BC를 먼저 곱하고 A를 곱하는 경우 A(BC)에 필요한 곱셈 연산의 수는 3×2×6 + 5×3×6 = 36 + 90 = 126번이다.

같은 곱셈이지만, 곱셈을 하는 순서에 따라서 곱셈 연산의 수가 달라진다.

행렬 N개의 크기가 주어졌을 때, 모든 행렬을 곱하는데 필요한 곱셈 연산 횟수의 최솟값을 구하는 프로그램을 작성하시오. 입력으로 주어진 행렬의 순서를 바꾸면 안 된다.

입력

첫째 줄에 행렬의 개수 N(1 ≤ N ≤ 500)이 주어진다.

둘째 줄부터 N개 줄에는 행렬의 크기 r과 c가 주어진다. (1 ≤ r, c ≤ 500)

항상 순서대로 곱셈을 할 수 있는 크기만 입력으로 주어진다.

출력

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

 

 

eunchanee.tistory.com/293

(백준 c++)11066 파일 합치기

DP 문제.

위 링크에 있는 문제와 비슷하다.

부분마다 행렬의 곱셈을 진행하면서, 부분에 대해 최솟값을 DP 테이블에 저장한다.

 

ABCD 행렬을 예를 들어본다.

	A	B	C	D
A	x	(A * B)	((A * B) * C) or (A * (B * C)	ABCD 곱셈의 최솟값
B		x	(B * C)	((B * C) * D) or (B * (C * D))
C			x	(C * D)
D				x

DP 테이블을 시각화 하면 위와 같다.

 

순서대로 따라가보자.

1) A * B 결과가 (1, 1)에 들어간다.

2) B * C 결과가 (2, 3)에 들어간다.

3) (1, 3)에는 ((A * B) * C)와 (A * (B * C))의 결과 중 작은 값이 들어간다.

- (A * B)의 결과는 (1, 1),

- (B * C)의 결과는 (2, 3)에 존재한다. 그렇기 때문에 중복된 계산은 하지 않게 된다.

4) D 열도 1 ~ 3번과 마찬가지로 계산하게 되며, 최종적으로는 (1, 4)에 정답이 들어간다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <climits>

using namespace std;

int main(void){
    int N;

    cin >> N;

    vector<pair<int, int>> arr(N + 1);
    vector<vector<pair<pair<int, int>, int>>> dp(N + 1, vector<pair<pair<int, int>, int>>(N + 1));

    for(int i = 1; i <= N; i++){
        int r, c;
        
        cin >> r >> c;
        arr[i] = make_pair(r, c);
    }

    //각 부분마다 최소값을 저장
    for(int i = 1; i < N; i++){
        for(int x = 1; x + i <= N; x++){
            int y = x + i;
            dp[x][y].second = INT_MAX;

            for(int j = x; j < y; j++){
                dp[x][y].second = min(dp[x][y].second, dp[x][j].second + dp[j + 1][y].second + arr[x].first * arr[j].second * arr[y].second);
            }
        }
    }
    
    cout << dp[1][N].second << endl;

    return 0;
}