[백준 C++] 11049번: 행렬 곱셈 순서(matrix chain multiplication)

1.문제

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

2. Solved.ac 난이도

3. 활용 알고리즘:  DP

4. 틀린 이유: .

DP는 더 작은 수에서부터 계산해보면서
무작정 구현보다 그림을 먼저 그려보고 점화식을 세워보기

---

매트릭스 체인 멀티플리케이션이라는 알고리즘을 사용하여 풀 수 있는 문제였고,

학교에서 수업시간에 배운 알고리즘이라 바로 적용할 수 있었다.

해당 수도코드를 이용하라고 수업시간에 배우긴 했지만,

for loop 조건문이 너무 더러워지기도 하고, 변수 많이 사용하는걸 별로 안좋앟서 l변수는 없에고 내 마음대로 구현해사용했다. 

 

최종 정답 코드

처음엔 그래프형 union& find를 써야한다는 생각을 하지 못했다.

때문에 일단 brute force로

#include <iostream>
#include <climits>
using namespace std;

int mat[501];
int com[501][501];
int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n,r,c;
	int i = 0;
	cin >> n;
	for (; i < n; i++) {
		cin >> r>>c;
		mat[i]=r;
	}
	mat[i] = c;
	int comp;
	for (int j = 1; j < n; j++) {
		for (int i = 1; j+i <= n; i++) {
			int comp,min=INT_MAX;
			int kk=j;
			for (int k = i; k < i + j;k++) {
				comp= com[i][k] + com[k + 1][i + j] + mat[i - 1] * mat[k] * mat[i + j];
				if (min > comp) {
					min = comp;
					kk = k;
				}
			}
			com[i][i + j] = min;
		}
	}
	cout << com[1][n];


	return 0;
}