(백준/ C++) 11049 - 행렬 곱셈 순서 / 다이나믹 프로그래밍

 

"(백준/ C++) 11049 - 행렬 곱셈 순서 / 다이나믹 프로그래밍"

---

 

해도해도 어려운 DP .. 혼자 못 풀었다. 유투브 설명 보고 풀었다 .. ㅠㅠ

 

핵심은 AEH 사이의 (ABCDE) (FGH)가 어떠한 방법으로 연산을 했든지 간에 (ABCDE) 의 최종행렬의 크기는 { a , f } (FGH)의 최종행렬 크기는 { f , i }가 된다. 라는 사실이다. 

 

점화식:  a x f x i + Func(x , k) + Func (k+1, y)  

---

 

어떻게 곱셈을 하든, Row[x] x Col[k] x Col[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;
}

 

 

2년전 ㅋㅋ ㅠㅠ;; 게으름뱅이 .. 다시 돌아오다 ..