[c++] 백준 11049 - 행렬 곱셈 순서(dp, 메모이제이션)

0. [c++] 백준  -

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

1. 풀이

동적계획법을 활용해서 문제를 풀어보자.

1) 우선, dp함수에서 곱셈 연산의 횟수의 최솟값을 구할 범위를 인자로 받는다.

2) 받은 인자를 모든 구간에서 쪼개어 계산을 하며 최솟값을 구해주자. (쪼개는 것은 두개의 큰 행렬로 나뉘게 되는 것이고, 나누면서 두개의 행렬 곱셈 연산 횟수를 더해준다.)

3) 이때, 반복되는 연산이 발생하게 되는데, 이를 막기위해 메모이제이션을 활용하자(한번 구한 값을 메모이제이션 하지 않는다면, 연산은 대략 N!이 넘게 되고 시간 초과를 하게 된다.)

2. 소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

#include<iostream> #include<algorithm> #include<vector>   using namespace std;   typedef unsigned long long ull;   int cache[501][501]; vector<pair<int, int> > arr; int N; int INF = 2147483647;   int dp(int begin, int end) {     int& ret = cache[begin][end];     if (ret != 0)         return ret;       if (begin == end)         return 0;       ret = INF;       for (int i = begin; i < end; i++) {         //하나의 행렬을 두개의 행렬로 나누어주자.         //그러면서 두개의 행렬을 곱한 값을 더해주는 것이 포인트이다.         ret = min(ret, dp(begin, i) + dp(i + 1, end) + arr[begin].first * arr[i].second * arr[end].second);     }          return ret; }   int main() {     ios_base::sync_with_stdio(0);     cin.tie(0);       int a, b;     cin >> N;     for (int i = 0; i < N; i++) {         cin >> a >> b;         arr.push_back({ a,b });     }       int ret = dp(0,N-1);                  cout << ret;     return 0; } Colored by Color Scripter

cs

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!