[백준 2156번] 포도주 시식 c++

https://www.acmicpc.net/problem/2156

2156번: 포도주 시식

 

계단오르기랑 비슷한 문제임

근데 이건 1번째 옆에있는거, 2번째 옆에있는것 고르는걸 넘어서

3번쨰 옆 4번째옆 까지 다 고려해야함

그래서 grape함수안에 for문으로 전부 순회하는 코드를 넣었음

 

 

 

내가푼 안좋은 탑다운(안좋은 코드, 코드싸개짓 했음)

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
 
int n;
int arr[10001];
int dp[10001][3];
 
//x== 현재 위치 cnt ==현재 몇 번째 연속된 잔인지
int grape(int x, int cnt) {
 
    if (x == n) return arr[n];
    if (x == n + 1) return 0;
 
    int& ret = dp[x][cnt];
 
    if (ret != -1) return ret;
 
 
    if (cnt == 2) {
        ret = grape(x + 2, 1);
        for (int i = 3; i <= n - x; i++)
            ret = max(ret, grape(x + i, 1));
        ret = arr[x] + ret;
        return ret;
    }
 
    ret = max(grape(x + 1, cnt + 1), grape(x + 2, 1));
    for (int i = 3; i <= n - x; i++)
        ret = max(grape(x + i, cnt + 1), ret);
    ret = arr[x] + ret;
 
    return ret;
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> arr[i];
 
    memset(dp, -1, sizeof(dp));
    cout << grape(0, 0);
 
    return 0;
}
 
 

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
 
int n;
int arr[10001];
int dp[10001];
 
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> arr[i];
 
    for (int i = 1; i <= n; i++)
        dp[i] = max(dp[i - 2] + arr[i], max(dp[i - 3] + arr[i] + arr[i - 1], dp[i - 1]));
 
    cout << dp[n];
 
    return 0;
}