솔직히 완전히 이해는 못해서 다음에 다시 풀라고 하면 한참 걸릴 것 같다.
저번에 풀었던 계단 오르기와 비슷한 문제인데, 풀이 방식에는 약간의 차이가 있다.
이유는 문제 조건이 다르기 때문인데,
포도주가 0만큼 들어있을 수 있다는 점과
마지막 포도주를 마시지 않아도 된다는 점이 계단 오르기 문제와 다르다.
따라서 그래서 두 번 건너뛰는 경우도 고려해야 한다.
가능한 선택지는 아래와 같다.
1. 현재 포도주를 마시지 않는 경우
dp[i] = dp[i - 1]
2. 현재 포도주를 마시고, 이전(i-1) 포도주는 마시지 않는 경우
dp[i] = dp[i - 2] + gr[i]
3. 현재 포도주와 이전(i-1) 포도주를 모두 마시고, (i-2) 포도주는 마시지 않는 경우
dp[i] = dp[i - 3] + gr[i - 1] + gr[i]
#include <iostream>
#include <algorithm>
using namespace std;
int gr[10001];
int dp[10001];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> gr[i];
dp[1] = gr[1];
dp[2] = gr[1] + gr[2];
dp[3] = max({ dp[2], gr[1] + gr[3], gr[2] + gr[3] });
for (int i = 4; i <= n; i++) {
dp[i] = max({ dp[i - 1], dp[i - 2] + gr[i], dp[i - 3] + gr[i - 1] + gr[i] });
}
cout << dp[n];
return 0;
}
실버도 어려우면 엇덕하니.