(백준/ C++) 11049 - 행렬 곱셈 순서 / 다이나믹 프로그래밍📃 coding test/◽ 백준2024. 7. 18. 12:48
Table of Contents
728x90
"(백준/ C++) 11049 - 행렬 곱셈 순서 / 다이나믹 프로그래밍"
해도해도 어려운 DP .. 혼자 못 풀었다. 유투브 설명 보고 풀었다 .. ㅠㅠ
핵심은 AEH 사이의 (ABCDE) (FGH)가 어떠한 방법으로 연산을 했든지 간에 (ABCDE) 의 최종행렬의 크기는 { a , f } (FGH)의 최종행렬 크기는 { f , i }가 된다. 라는 사실이다.
점화식: a x f x i + Func(x , k) + Func (k+1, y)
//== [ 행렬 곱셈 순서 ] ==
#include <iostream>
#include <limits>
#include <algorithm>
using namespace std;
int col[500], row[500];
int dp[500][500];
int func(int idx_x, int idx_y)
{
if (dp[idx_x][idx_y])
return dp[idx_x][idx_y];
if (idx_x == idx_y)
return 0;
int mm = INT_MAX;
for (int j = idx_x; j < idx_y; ++j)
// (j == idx_x) 경우는 ABCD 있다면 AB경우.
{
mm = min(mm, row[idx_x] * col[j] * col[idx_y] + func(idx_x, j) + func(j + 1, idx_y));
}
return dp[idx_x][idx_y] = mm;
}
int main(void)
{
int n;
cin >> n;
for (int i = 0; i < n; ++i)
cin >> row[i] >> col[i];
cout << func(0, n - 1);
return 0;
}

728x90
'📃 coding test > ◽ 백준' 카테고리의 다른 글
(백준/ C++) 9095 - 1, 2, 3 더하기 / 다이나믹 프로그래밍, 재귀 (0) | 2024.07.19 |
---|---|
(백준/ C++) 1520 - 내리막길 / 다이나믹 프로그래밍 (1) | 2024.07.18 |
(백준/ C++) 7579 - 앱 / 다이나믹 프로그래밍 (0) | 2024.07.12 |
(백준/ C++) 1106 - 호텔 / 다이나믹 프로그래밍 (0) | 2024.07.11 |
(백준/ C++) 2629 - 양팔저울 (0) | 2024.07.09 |
@핑크코냥 :: 핑크코냥
안 하는 것 보다 낫겠지
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!