[BAEKJOON] 11049 행렬의 곱셈 순서 - 연쇄 행렬 최소 곱셈 알고리즘

#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int size, input, j; scanf("%d", &size); vector<int>d(1001); vector<vector<long long>>M(1001, vector<long long>(1001)); for (int j = 0; j < size; j++) { if (j == 0) scanf("%d %d", &d[0], &d[1]); else scanf("%d %d", &input, &d[j + 1]); } for (int diagonal = 0; diagonal < size; diagonal++) { for (int i = 1; i + diagonal <= size; i++) { j = i + diagonal; if (j == i) { M[i][j] = 0; continue; } M[i][j] = 2e9; for (int k = i; k <= j - 1; k++) M[i][j] = min(M[i][j], M[i][k] + M[k + 1][j] + d[i - 1] * d[k] * d[j]); } } printf("%lld", M[1][size]); return 0; }

정말 어려웠다..

일단 나는 수학을 잘 못하기 때문에 이해하는 데 오랜 시간이 걸렸다

http://huiyu.tistory.com/entry/DP-%EC%97%B0%EC%87%84%ED%96%89%EB%A0%AC-%EC%B5%9C%EC%86%8C%EA%B3%B1%EC%85%88-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

이 블로그의 설명이 가장 이해가 잘됬다 (짱짱)

전체적인 개념은

행렬 1에서 4까지 계산할때

1에서2까지 2에서 4까지 그리고 1에서 2 그리고 4까지 합치는 비용을 더하고

1에서 3까지 3에서 4까지 그리고 1에서 3 그리고 4까지 합치는 비용의 최소를 계산하는 것이다.

+)

연쇄 행렬의 최소 곱셈 계산 방향

1,1 / 2,2 ...에서는 0을 저장하고

1,2에 가서 1,1+2,2+d0*d1*d2

2,3에 가서 2,2+3,3+d0*d2*d3

3,4에 가서 ....

반복해서 계산해주면 된다

-----------

1. d배열의 저장

만약 10*2 2*3 3*4

라면

d배열에는

d[0] = 10 / d[1] = 2 / d[2] = 3 / d[3] =4

라고 저장이 된다

2. 3중 반복문

diagonal은 어느 대각선을 계산할지 더해주는 것이다

x=y인 곳부터 시작해서 위로 올라가면서 대각선으로 계산한다

i는 x축 j는 y축이다!

1 2 3 4 가 있을 때

(1 2) 3 4

(1 2) (3 4)

(1 2 3 4)

이렇게 묶을 수도 있고

(1 2) 3 4

((1 2) 3) 4

(((1 2) 3) 4)

이렇게 묶을 수도 있다

이렇게 묶는 방법에 따라 정답이 달라질때

보통 연쇄 행렬 최소 곱셈 알고리즘을 쓰는 것 같다