일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- IndexedTree
- LCA
- BinarySearch
- FenwickTree
- greedy
- Tree
- topologicalsort
- mergesorttree
- BFS
- Math
- DFS
- Flow
- backtracking
- Dijkstra
- ArticulationPoint
- TwoPointers
- Implementation
- LIS
- Floyd
- KMP
- SlidingWindow
- Bellman-Ford
- ShortestPath
- MST
- Union-Find
- Bridge
- DP
- scc
- 2-sat
- Sweeping
- Today
- Total
정리충의 정리노트
[백준] 11049: 행렬 곱셈 순서 본문
0. 문제 주소
https://www.acmicpc.net/problem/11049
1. 풀이
2차원 배열을 이용하여 모든 구간별 정보를 메모이제이션 하는 dp 문제.
다시 말해서, i번째 행렬부터 j번째 행렬까지 곱했을 때의 최소 곱셈 횟수를 저장할 것이기 때문에, 이 정보들을 이용하기 위해선 곱셈 형태를 큰 부분 두 개로 나누어야 한다.
A, B, C, D 4개의 행렬이 있다고 가정해 보자.
메모이제이션을 통해 A ~ C , 그리고 B ~ D 를 곱할 때의 최소 곱셈 횟수를 기억해뒀다고 가정하면, 가능한 경우는
1. (A B C) x D ----> A B C의 최소 곱셈 횟수 + D의 최소 곱셈 횟수 (= 0) + ABC x D에서 발생하는 곱셈 횟수
2. (A B) x (C D) ----> A B의 최소 곱셈 횟수 + C D의 최소 곱셈 횟수 + AB x CD에서 발생하는 곱셈 횟수
3. A x (B C D) ----> A의 최소 곱셈 횟수 (= 0) + B C D의 최소 곱셈 횟수 + A x BCD에서 발생하는 곱셈 횟수
라고 정리할 수 있다.
참고로 여기서 dp[i][j] 는 i번째 행렬부터 j번째 행렬까지 곱했을 때의 최소 곱셈 횟수를 저장하기 때문에,
i <= j를 만족하게 되고, 따라서 dp 테이블은 upper triangular의 형태를 갖게 된다.
i == j일 때는 행렬이 하나일 때이므로, 별다른 횟수가 필요없다. 즉 dp[i][j] == 0 (i == j)
i == j-1일 때는, 바로 인접한 행렬 두 개를 곱할 때이므로,
가능한 곱셈 방법은 한 가지고 바로 그 때의 횟수가 최소 곱셈 횟수가 된다.
이렇게 두 가지의 초기 케이스를 초기화 해주고, 아래 코드와 같이 dp 테이블을 채워준 후, dp[1][N]에 저장된 값을 출력하면 된다.
2. 풀이 코드
* 유의할 점
1. 중간 과정에서 혹시 발생할지도 모를 오버플로우에 대비하여 long long 자료형 사용
2. mat 배열은 pair<long long, long long> 자료형 이용, first에는 row, second에는 column값 저장
3. 대각 성분, 그리고 그 바로 위 성분은 미리 초기화.
#include <bits/stdc++.h>
#define MAX 505
#define ll long long
#define pll pair<ll, ll>
#define INF 1e11
using namespace std;
int N;
pll mat[MAX]; // first : row, second : column
ll dp[MAX][MAX];
int main(){
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif // ONLINE_JUDGE
scanf("%d", &N);
for (int i=1;i<=N;i++){
ll r, c;
scanf("%lld %lld", &r, &c);
mat[i] = pll(r, c);
}
for (int i=1;i<N;i++){
dp[i][i+1] = mat[i].first * mat[i].second * mat[i+1].second;
}
for (int d=2;d<=N-1;d++){
for (int i=1;i<=N-d;i++){
ll curr_min = INF;
int j = i + d;
for (int k=i;k<j;k++){
curr_min = min(curr_min, mat[i].first * mat[k].second * mat[j].second + dp[i][k] + dp[k+1][j]);
}
dp[i][i+d] = curr_min;
}
}
printf("%lld\n", dp[1][N]);
}
'PS > DP' 카테고리의 다른 글
[백준] 2533: 사회망 서비스 (0) | 2020.01.24 |
---|---|
[백준] 11066: 파일 합치기 (0) | 2020.01.24 |
[백준] 9084: 동전 (1) | 2020.01.20 |
[백준] 9251: LCS (0) | 2020.01.19 |
[백준] 2169: 로봇 조종하기 (0) | 2020.01.19 |