[백준][11049] 행렬 곱셈 순서

이 포스트는 백준 사이트의 행렬 곱셈 순서 문제 풀이입니다.

문제

해결 과정

이 문제는 여러 작은 문제로 나워서 해결하는 DP(다이나믹 프로그래밍) 방법을 사용해 해결할 수 있습니다.

문제를 해결하기 위해서 먼저, DP 테이블을 사용하였습니다.
2차원 배열의 테이블은 DP_table[a][b]에서 a번째 행렬부터 b번째 행렬까지의 곱 중 최소 곱셈 횟수를 기록하였습니다.
따라서 모든 연산이 완료된 후 DP_table[1][N]을 출력하면 N개의 행렬을 곱할 때의 최소 곱셈 횟수를 알 수 있습니다.

코드 구현

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

#define MAX 510

using namespace std;

int main()
{
	int N;
	cin.tie(0);
	cin >> N;

    vector<vector<int>> matrix(MAX, vector<int>(2, 0));
    vector<vector<int>> DP_table(MAX, vector<int>(MAX, 0));

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

	for (int i = 1; i < N; ++i) {
		for (int j = 1; i + j <= N; ++j) {
			DP_table[j][i + j] = 2e9;

			for (int k = j; k <= i + j; ++k) {
                int new_count = DP_table[j][k] + DP_table[k + 1][i + j]
                                + (matrix[j][0] * matrix[k][1] * matrix[i + j][1]);

				DP_table[j][i + j] = min(DP_table[j][i + j], new_count);
			}
		}
	}

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

실행 결과

참고

[C/C++] 백준 11049번 - 행렬 곱셈 순서 (DP), 코딩공부일지님 블로그