[백준] 11049-행렬 곱셈 순서(C++)

문제링크:https://www.acmicpc.net/problem/11049

11049번: 행렬 곱셈 순서

 

11066번 파일합치기와 짝궁인 문제 입니다.

dp 문제이고 두가지 푸는 방식이 있습니다.

 

• 1. down-up 방식 ->  대각선 dp 라는 방법을 통해서 삼중포문을 통해서 구현하는 방법입니다. 시간이 빠릅니다.
• 2. up-down 방식 -> 재귀를 통해서 아래의 dp값들을 구하고 최종 결과값을 구하는 형태입니다. 직관적인 것이 장점입니다. 

점화식을 유추해야합니다. 우선은 dp[i][j]는 i부터 j까지의 곱셈연산의 최소값이라고 가정합시다.

이때 dp[1][1] = 0이고 dp[1][2] = 5 * 3 * 2가 됩니다.

 

 

입력이 

4

5 3

3 2

2 6

6 4

일때 표로 나타내면 

	1	2	3	4
1	0	5*3*2 =30	90	118
2		0	3*2*6 =36	72
3			0	2*6*4 =48
4				0

dp[1][3] 일때 5*3*2 + 5*2*6 = 90이 3*2*6 + 5*3*6보다 작기 때문에 90이 됩니다.

이처럼 이전 dp값들을 통해 비교하며 결과를 도출해야합니다. 

 

점화식은 dp[i][j] = dp[i][k] + dp[k+1][j] + arr[i][0]*arr[k][1]*arr[j][1] 입니다. ( k는 i부터 j까지 반복)

모든 지점에서 값을 비교해주어야 하기때문에 i부터 j 까지 k값을 반복해주어야 하는 것입니다.

dp[i][j] 는 dp[i][k] 구간과 dp [k+1][j] 의 합에다가 두 부분을 잇는 arr[i][0]*arr[k][1]*arr[j][1] 의 합입니다. 

 

 

저는 up-down 방식으로 문제를 해결했습니다.

 

#include <iostream>
#include <cstring>
using namespace std;

int n = 0;
int arr[501][2];
int dp[501][501];

int  sol(int st,int ed) {
	if (st == ed) return dp[st][ed] = 0;
	if (st + 1 == ed) return dp[st][ed] = arr[st][0] * arr[st][1] * arr[ed][1];

	int &ret = dp[st][ed];

	if (ret != -1)
		return ret;

	for (int i = st; i < ed; i++) {
		int temp = sol(st, i) + sol(i + 1, ed) + arr[st][0] * arr[i][1] * arr[ed][1];
		if (ret > temp || ret == -1) ret = temp;
	}

	return ret;
}


int main() {
	cin >> n;

	for (int i = 1; i <= n; i++)
		cin >> arr[i][0] >> arr[i][1];

	memset(dp, -1, sizeof(dp));
	sol(1, n);


	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++)
			cout << dp[i][j] << ' ';
		cout << endl;
	}
	cout << dp[1][n] << endl;
	return 0;
}

 

문제를 풀면서 아직 많이 부족하다는 것을 느꼈습니다. 

더 노력하겠습니다.

 

-----추가----

 

 

점화식에 대해서 많이 고민해봤습니다.

for (int i = st; i < ed; i++) {
		int temp = sol(st, i) + sol(i + 1, ed) + arr[st][0] * arr[i][1] * arr[ed][1];
		if (ret > temp || ret == -1) ret = temp;
	}

 

 

 

처음 sol(1,3) 이라면,

dp[1][3] = min(sol(1,1) + sol(2,3) + arr[1][0] + arr[1][1](arr[2][0]) + arr[3][1], 자기자신)

dp[1][3] = min(sol(2,1) + sol(3,3) + arr[1][0] + arr[2][1](arr[3][0]) + arr[3][1], 자기자신)

 

이 규칙대로 변화가 일어나는데, dp[i][j]가 i부터j까지의 최소값이기 때문입니다.