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

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보다 작거나 같다.

---

풀이)

11066 파일합치기 문제처럼 dp를 사용해서 풀면 되는 문제이다.

점화식

matrix[i][0] = i번째 행렬의 r      /    matrix[i][1] = i번째 행렬의 c

dp[i][j] = 행렬 i ~ j 까지 곱했을 시 최소 곱셈 횟수

(i<=k<j)

dp[i][j] = min(dp[i][k] + dp[k+1][j] * matrix[i][0] * matrix[k+1][0](= matrix[k][1]) * matrix[j][1])

주의사항

dp[][]배열의 초기값은 나올 수 없는 최대값으로 설정

dp[i][i] = 자기자신의 값은 0으로 설정

코드)

#include <stdio.h>
#include <algorithm>
using namespace std;
 
#define INF 999999999;
int N, r, c;
int matrix[501][2];
long long dp[501][501];
 
int main() {
    scanf("%d", &N);
    
    for (int i = 1; i <= N; i++) {
        scanf("%d %d", &r, &c);
        matrix[i][0] = r;
        matrix[i][1] = c;
    }
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) dp[i][j] = INF;
        dp[i][i] = 0;
    }
    for (int i = 1; i <= N - 1; i++) {
        dp[i][i + 1] = matrix[i][0] * matrix[i][1] * matrix[i + 1][1];
    }
    for (int len = 2; len < N; len++) {//행렬곱셈길이
 
        for (int i = 1; i <= N - len; i++) {//시작위치
 
            int j = i + len;//시작위치 + 곱셈길이 = 마지막위치
 
            for (int k = i; k < j; k++) {//중간위치
                dp[i][j] = min(dp[i][j],dp[i][k] + dp[k+1][j] + matrix[i][0] * matrix[k+1][0] * matrix[j][1]);
            }
 
        }
    }
    printf("%lld", dp[1][N]);
    return 0;
}