728x90
반응형
1. 문제
https://www.acmicpc.net/problem/11049
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
'백준 알고리즘 > 백준 CLASS 5' 카테고리의 다른 글
[백준 C++] 20303번: 할로윈의 양아치 (1) | 2024.04.03 |
---|---|
[백준 C++] 16724: 피리 부는 사나이 (0) | 2024.03.25 |
[백준 C++] 9466번: 텀 프로젝트 (1) | 2023.12.03 |
[백준 C++] 7579번: 앱 (0) | 2023.12.03 |
[백준 C++] 4386번: 별자리 만들기 (0) | 2023.10.22 |