백준11049 행렬 곱셈 순서

작성일 | In

문제 링크

  • http://icpc.me/11049

사용 알고리즘

  • DP

시간복잡도

  • O(n3)

풀이

dp[i][j]를 i번째부터 j번째 행렬까지의 곱의 최소 연산 횟수라고 정의하자.
Floyd Warshall Algorithm과 비슷하게 처리하면 된다.

먼저 인접한 행렬의 최소 연산 횟수는 직접 구하고, 나머지 경우에는 3중 for문을 이용해 구합니다.
3중 for문의 가장 바깥쪽에서 i와 j의 차를 의미하는 m을 2부터 n까지 돌리고, 두 번째 for문은 i값을 돌립니다.
j값은 m과 i를 이용해 구할 수 있습니다. 세 번째 for문에서는 경유점을 의미하는 k를 [i, j) 범위에서 돌립니다.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;

int arr[510][2];
int dp[510][510];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n;
	for(int i=1; i<=n; i++){
		cin >> arr[i][0] >> arr[i][1];
	}

	for(int i=1; i<n; i++){
		dp[i][i+1] = arr[i][0] * arr[i][1] * arr[i+1][1];
	}

	for(int m=2; m<=n; m++){ //차
		for(int i=1; i<=n-m; i++){ //시작
			int j = i+m;
			for(int k=i; k<j; k++){
				int res = dp[i][k] + dp[k+1][j] + arr[i][0] * arr[k][1] * arr[j][1];
				if(!dp[i][j] || dp[i][j] > res) dp[i][j] = res;
			}
		}
	}
	cout << dp[1][n];
}