[Gold III] 행렬 곱셈 순서 - 11049

문제 링크

문제 링크

성능 요약

메모리: 3004 KB, 시간: 28 ms

문제 설명

크기가 N×M인 행렬 A와 M×K인 B를 곱할 때 필요한 곱셈 연산의 수는 총 N×M×K번이다. 행렬 N개를 곱하는데 필요한 곱셈 연산의 수는 행렬을 곱하는 순서에 따라 달라지게 된다.

예를 들어, A의 크기가 5×3이고, B의 크기가 3×2, C의 크기가 2×6인 경우에 행렬의 곱 ABC를 구하는 경우를 생각해보자.

• AB를 먼저 곱하고 C를 곱하는 경우 (AB)C에 필요한 곱셈 연산의 수는 5×3×2 + 5×2×6 = 30 + 60 = 90번이다.
• BC를 먼저 곱하고 A를 곱하는 경우 A(BC)에 필요한 곱셈 연산의 수는 3×2×6 + 5×3×6 = 36 + 90 = 126번이다.

같은 곱셈이지만, 곱셈을 하는 순서에 따라서 곱셈 연산의 수가 달라진다.

행렬 N개의 크기가 주어졌을 때, 모든 행렬을 곱하는데 필요한 곱셈 연산 횟수의 최솟값을 구하는 프로그램을 작성하시오. 입력으로 주어진 행렬의 순서를 바꾸면 안 된다.

입력

첫째 줄에 행렬의 개수 N(1 ≤ N ≤ 500)이 주어진다.

둘째 줄부터 N개 줄에는 행렬의 크기 r과 c가 주어진다. (1 ≤ r, c ≤ 500)

항상 순서대로 곱셈을 할 수 있는 크기만 입력으로 주어진다.

출력

첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 2³¹-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 2³¹-1보다 작거나 같다.

코드

#include <iostream>
#include <algorithm>

using namespace std;

int N;
pair<int, int> rc[501];
int dp[501][501]; // dp[i][j]: i번부터 j번 행렬까지 최소 곱셈 연산 횟수

int main() {
	cin.tie(0)->sync_with_stdio(0);

	cin >> N;

	// 행렬 입력 받기
	for (int i = 0; i < N; i++) {
		cin >> rc[i].first >> rc[i].second;
	}

	// DP 배열 초기화
	for (int i = 0; i < N; i++) {
		dp[i][i] = 0; // 단일 행렬은 곱셈 연산 필요 없음
	}

	// 점화식 계산
	for (int len = 2; len <= N; len++) { // 부분 문제 크기
		for (int i = 0; i <= N - len; i++) {
			int j = i + len - 1; 
			dp[i][i + len - 1] = 21e8;

			// 최적의 분할점 k 탐색
			for (int k = i; k < i + len - 1; k++) {
				int cost = dp[i][k] + dp[k + 1][i + len - 1] + rc[i].first * rc[k].second * rc[i + len - 1].second;
				dp[i][i + len - 1] = min(dp[i][i + len - 1], cost);
			}
		}
	}

	// 결과 출력
	cout << dp[0][N - 1] << "\n"; // 전체 행렬 곱셈의 최소 연산 횟수

	return 0;
}