11049번: 행렬 곱셈 순서
첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같
www.acmicpc.net
N * M 행렬과 M * K 행렬을 곱할때는 N * M * K번의 연산이 필요합니다.
이 공식을 이용해서 여러개의 행렬을 곱하는데 필요한 곱셈 연산의 수를 최소로 해야합니다.
입력으로는 순서대로 곱셈이 가능하게 주어지므로 순서대로 연산을 할 수 있습니다.
저는 3중for문을 사용하였습니다.
i는 간격, x는 시작 인덱스, y는 중간 인덱스, k는 끝 인덱스를 나타내었습니다.
dp[x][k]는 dp[x][y] + dp[y + 1][k]
즉, (x ~ y번째 행렬을 곱할 때 연산의 최솟값) + (y + 1 ~ k번째 행렬을 곱할 때 연산의 최솟값) 에다가
x ~ y번째가 합쳐있는 행렬과 y + 1 ~ k번째가 합쳐있는 행렬을 곱할 때 필요한 연산을 더해주어야합니다.
그러면 점화식은 dp[x][k] = min(dp[x][k], dp[x][y] + dp[y + 1][k] + list[x].first * list[y].second * list[k].secod) 가 될 수 있습니다.
출력은 dp[1][N] (1 ~ N번째 행렬을 곱할 때 연산의 최솟값)로 해주시면 됩니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
#include <iostream>
#include <algorithm>
using namespace std;
pair<int, int> list[501];
int dp[501][501];
int N;
void func() {
for (int i = 1; i < N; i++) {
for (int x = 1; x + i <= N; x++) {
int k = x + i;
for (int y = x; y < k; y++) {
if (!dp[x][y])
dp[x][k] = dp[x][y] + dp[y + 1][k] + list[x].first * list[y].second * list[k].second;
else
dp[x][k] = min(dp[x][k], dp[x][y] + dp[y + 1][k] + list[x].first * list[y].second * list[k].second);
}
}
}
cout << dp[1][N] << '\n';
}
void input() {
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> list[i].first >> list[i].second;
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
'algorithm > dp' 카테고리의 다른 글
| boj 17404 RGB거리 2 (0) | 2021.02.28 |
|---|---|
| boj 2616 소형기관차 (0) | 2021.02.27 |
| boj 1915 가장 큰 정사각형 (0) | 2021.02.20 |
| boj 1912 연속합 (0) | 2021.02.18 |
| boj 10211 Maximum Subarray (0) | 2021.02.18 |