※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※
이번에 볼 문제는 백준 11049번 문제인 행렬 곱셈 순서이다.
문제는 아래 링크를 확인하자.
https://www.acmicpc.net/problem/11049
11049번: 행렬 곱셈 순서
첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같
www.acmicpc.net
연산 횟수가 최솟값이 되게 행렬을 곱해나가는 순서가 하나 있다고 생각해보자. 이 순서를 거꾸로 따라나가면 두 개의 행렬을 마지막에 곱하는 것으로 행렬의 곱셈 계산을 마무리짓는다는 것을 알 수 있다. 이 때, 이 곱셈을 이루고 있는 두 행렬을 만드는데 필요한 횟수를 처음 문제와 똑같이 최소화해야할 것이라는 것을 확인하자.
따라서, 작은 구간의 행렬들을 곱하는 데에 필요한 최소 연산의 수를 dp를 이용하여 구해나가는 것으로 문제를 해결할 수 있다.
아래는 제출한 소스코드이다.
#include <iostream>
using namespace std;
int dp[500][500];
int arr[2][500];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int N; cin >> N;
for (int i = 0; i < N; i++) {
cin >> arr[0][i] >> arr[1][i];
}
for (int d = 1; d < N; d++) {
for (int R = d; R < N; R++) {
int L = R - d;
dp[L][R] = 2147483647;
for (int k = L; k < R; k++) {
dp[L][R] = min(dp[L][R], dp[L][k] + dp[k + 1][R] + arr[0][L] * arr[1][k] * arr[1][R]);
}
}
}
cout << dp[0][N - 1];
}
728x90
'BOJ' 카테고리의 다른 글
[BOJ 2514 // C++] 자동분무기 (0) | 2021.12.24 |
---|---|
[BOJ 2513 // C++] 통학버스 (0) | 2021.12.23 |
[BOJ 3673 // C++] 나눌 수 있는 부분 수열 (0) | 2021.12.21 |
[BOJ 1743 // C++] 음식물 피하기 (0) | 2021.12.20 |
[BOJ 5567 // C++] 결혼식 (0) | 2021.12.19 |