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

https://www.acmicpc.net/problem/11049

11049번: 행렬 곱셈 순서

문제

크기가 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)

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

출력

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

---

유명한 Chained Matrix Multiplication 문제이다.

dp[a][b]의 값은 a~b 번째 행렬을 곱하는데 든 최소비용으로 둔다.

arr[i]. first는 행의 크기 arr[i]. second는 열의 크기라고 할 때

dp[a][b]의 값은 a <=m <=b 인 m에 대하여 dp[a][m] + dp[m+1][b] + arr[a]. first *arr[m]. second *arr[b]. second의 값들 중 최솟값이 된다.

#include <iostream>
#define MAX 8888888888
using namespace std;
long long dp[510][510] = { 0 };
int N,a,b;
pair<int, int> arr[510];
int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> a >> b;
		arr[i] = { a,b };
	}
	for (int d = 1; d < N; d++) {
		for (int i = 1; i + d <= N; i++) {
			dp[i][i + d] = MAX;
			for (int j = i; j < i + d; j++) {
				dp[i][i + d] = min(dp[i][i + d], dp[i][j] + dp[j + 1][i + d] + arr[i].first * arr[j].second * arr[i+d].second);
			}
		}
	}
	
	cout << dp[1][N]; 

}

---

그래도 저번 문제에서 이와 비슷한 문제를 풀어서 점화식을 구하는 것은 어렵지 않았다. 하지만 j의 초기값을 i+1로 두고 시작해버려서 예제는 통과하지만 제출은 틀렸습니다가 여러 번 떴다. SWEA 문제는 문제 사이즈가 크고 예제도 많은데 구글링을 해도 안 나와서 반례 생각을 조금 오래 하게 되는데 백준 문제는 주어진 예제 말고는 떠오르지도 않고 구글링을 하면 바로바로 나와서 반례를 떠올리기 귀찮아하는 것 같다.