알고리즘
[알고리즘] c++ cpp 포도주 시식
keel_im
2020. 10. 6. 18:47
반응형
포인트
1. 다이나믹 프로그래밍의 이해
2. // 막잔을 기준으로 3번째 앞에 잔을 마시고, 2번째 앞에 잔을 건너뛰고 1번째 앞에 잔 + 막잔
// 막잔을 기준으로 2번째 앞에 잔을 마시고 + 막잔
// 막잔을 마시지 않고, 1번째 앞에 잔의 최댓값
🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다.
#include<iostream>
#include<cstring>
#define MAX 10001
using namespace std;
int n;
int map[MAX];
int d[MAX];
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> map[i];
d[0] = map[0] = 0;
d[1] = map[1];
d[2] = map[1] + map[2];
// 막잔을 기준으로 3번째 앞에 잔을 마시고, 2번째 앞에 잔을 건너뛰고 1번째 앞에 잔 + 막잔
// 막잔을 기준으로 2번째 앞에 잔을 마시고 + 막잔
// 막잔을 마시지 않고, 1번째 앞에 잔의 최댓값
for (int i = 3; i <= n; i++) d[i] = max(d[i - 3] + map[i - 1] + map[i], max(d[i - 2] + map[i], d[i - 1]));
cout << d[n] << endl;
return 0;
}
반응형