[백준]11049 행렬곱셈순서 #사선dp

1. 풀이

(1) 인접해있는 두 행렬부터 비교해가면서 점차 길이를 늘려간다.

(2) dp[i][j] : i번째 행렬에서 j번째 행렬까지 곱했을 때 나올 수 있는 최소연산

(3) 점화식(3중포문)

for l : i와 j의 차이. 1차이나는 것(인접한것) 부터 시작하여 늘려나간다

  for i : 시작점 찾기 (j는 끝점)

    for k : i와 j 사이에 구분점 선택

(ex l이 4이고, 2~6을 탐색할 때 (2,3:6),(2:3,4:6),(2:4,5:6) 중 가장 작은것을 (2:6)으로 선택)

​

2. 소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

// dp[i][j] : i에서 j행렬까지의 곱중 최소연산
int dp[501][501];

// list[i][0] : i행렬의 행, list[i][1] : i행렬의 열
int list[501][2];

int main() {
	int N;
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> list[i][0] >> list[i][1];
	}

	for (int l = 1; l <= N - 1; l++) {
		for (int i = 1; i <= N - l; i++) {
			int j = i + l;
			for (int k = i; k < j; k++) {
				int c = dp[i][k] + dp[k + 1][j] + (list[i][0] * list[k][1] * list[j][1]);
				if (dp[i][j] == 0 || dp[i][j] > c) {
					dp[i][j] = c;
				}
			}
		}
	}
	
	/* dp확인
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cout << dp[i][j] << " ";
		}
		cout << endl;
	}
	*/
	

	cout << dp[1][N];
	return 0;
}

 

<output>

0 30 90
0 0 36
0 0 0
90