백준 알고리즘/백준 CLASS 5
[백준 C++] 11049번: 행렬 곱셈 순서
code_killer
2023. 12. 9. 22:25
728x90
반응형
1. 문제
https://www.acmicpc.net/problem/11049
11049번: 행렬 곱셈 순서
첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같
www.acmicpc.net
2. 알고리즘 분류
- 다이나믹 프로그래밍
3. 소스 코드
#include <iostream>
#include <algorithm>
#define INF 987654321
using namespace std;
pair<int, int> matrix[501];
int dp[501][501];
int main()
{
// N : 행렬의 갯수 입력
int N, r, c, A, B, C;
cin >> N;
// 행렬 입력
for (int i = 1; i <= N; i++)
{
cin >> r >> c;
matrix[i] = { r, c };
}
// DP 풀이
// A X B 행렬 * B X C 행렬 = A X B X C
// dp[A][C] = A ~ C까지 최소 연산 수
for (int i = 1; i < N; i++)
{
for (int j = 1; i + j <= N; j++)
{
A = j;
C = j + i;
dp[A][C] = INF; // DP 초기화
for (int k = j; k <= C; k++)
{
B = k;
dp[A][C] = min(dp[A][C], dp[A][B] + dp[B + 1][C] + matrix[A].first * matrix[B].second * matrix[C].second);
}
}
}
cout << dp[1][N];
return 0;
}
728x90