단계별로 풀어보기 동적 계획법 1의 10단계 문제
2156번: 포도주 시식
효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고
www.acmicpc.net
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
int* grape = new int[n];
int** dp = new int*[n];
for (int i = 0; i < n; i++) {
dp[i] = new int[2];
}
for (int i = 0; i < n; i++) {
cin >> grape[i];
}
dp[0][0] = grape[0];
dp[0][1] = grape[0];
if (n > 1) {
dp[1][0] = grape[0] + grape[1];
dp[1][1] = grape[1];
}
for (int i = 2; i < n; i++) {
dp[i][0] = dp[i - 1][1] + grape[i];
int max = 0;
for (int j = i - 2; j >= 0; j--) {
for (int k = 0; k < 2; k++) {
if (dp[j][k] > max) {
max = dp[j][k];
}
}
}
dp[i][1] = max + grape[i];
}
int max = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < 2; j++) {
if (dp[i][j] > max) {
max = dp[i][j];
}
}
}
cout << max << endl;
return 0;
}배열 dp[i][0]에는 i-1번째 포도주를 마셨을 경우 최대 양을, dp[i][1]에는 i-1번째 포도주를 마시지 않았을 경우 가능한 최대 양을 저장했다.
2579번 계단오르기와 다른 점은 계단 오르기 문제는 반드시 마지막 계단을 밟아야 하지만 이 문제는 반드시 마지막 포도주를 마실 필요가 없다. 또, 계단오르기는 무조건 한 칸이나 두 칸씩 올라야 하지만 포도주 마시기는 여러 포도주를 뛰어넘고 안 마셔도 상관이 없다. 따라서 이 문제가 더 고려할 것이 많아 조금 더 복잡하다.
이렇게 2020년에 1월 24일에 풀고 두 달 반 후인 4월 11일에 다시 한 번 풀어보았다.
#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
vector<int> v(n);
for (int i = 0; i < n; i++) {
cin >> v[i];
}
vector<tuple<int, int, int>> dp(n);
dp[0] = make_tuple(0, v[0], v[0]);
if (n > 1) {
dp[1] = make_tuple(v[0], v[1], v[0] + v[1]);
}
for (int i = 2; i < n; i++) {
get<0>(dp[i]) = max(get<0>(dp[i - 1]), max(get<1>(dp[i - 1]), get<2>(dp[i - 1])));
get<1>(dp[i]) = get<0>(dp[i - 1]) + v[i];
get<2>(dp[i]) = get<1>(dp[i - 1]) + v[i];
}
cout << max(get<0>(dp[n - 1]), max(get<1>(dp[n - 1]), get<2>(dp[n - 1])));
return 0;
}
코드 길이도 더 짧고 시간도 더 적게 걸렸고 메모리도 더 적게 사용했다.
나는 잘 모르겠어도 나도 모르는 사이에 발전은 하나보다.
3-tuple을 만들어서 dp 벡터에 저장했다.
dp[i]에 저장된 튜플의 첫 번째 원소는 i번째 포도주를 마시지 않는 경우 중 최댓값을 저장한다. i번째 포도주를 마시지 않으므로 dp[i]에 저장된 3가지 숫자 중에 가장 큰 수를 그대로 가져온다.
dp[i]에 저장된 튜플의 두 번째 원소는 i번째 포도주를 마시되 i - 1번째 포도주는 마시지 않았을 경우 중 최댓값을 저장한다. i - 1번째 포도주는 마시지 않았어야 하므로 dp[i - 1]의 첫 번째 원소에 i번째 포도주를 더해준 값을 저장한다.
dp[i]에 저장된 튜플의 세 번째 원소는 i번째 포도주 연속으로 마시는 경우이다. 세 개를 연속으로 마시지는 못하므로 dp[i - 1]의 두 번째 원소에 i번째 포도주를 더해준 값을 저장한다.
'알고리즘 문제' 카테고리의 다른 글
| [백준] 2580번 스도쿠 (0) | 2020.01.25 |
|---|---|
| [백준] 2775번 부녀회장이 될테야 (0) | 2020.01.24 |
| [백준] 2579번 계단 오르기 (0) | 2020.01.24 |
| [백준] 2446번 별 찍기 - 9 (0) | 2020.01.22 |
| [백준] 2445번 별 찍기 - 8 (0) | 2020.01.22 |
