[BOJ2156 C++] 포도주 시식

실버 1 문제
질문 게시판에 포도주 시식이 아니고 포도주 시음이라는거 보고 웃겼다
별게 다 불편해 아주 ~ 문제나 풀것이지 ~

이게 전에 포스팅한 계단 오르기랑 진짜 똑같아 보이는데, 조건이 조금 달라지면서 또 까다롭더라 ..

조금만 바꿔서 될 것이 아니고 점화식을 다시 생각해봐야된다. (같은 소린가?)

조건은 다음과 같다.

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

연속으로 놓여있는 3잔을 모두 마실 수는 없다. 에서 비슷한 향기가 났지만 ..

너무 계단에 심취한 나머지 1칸 2칸 가는것도 똑같은줄 알았다.

N칸 뛰고 다음거 마셔도 된다 ...

예를 들면,

1000 1000 1 1 1000 1000 이렇게 있을 때,

1000 -> 1000 -> 1000 -> 1000 이렇게 마셔야 3개 연속으로 안마시고 가장 많이 마시는데,
1칸 2칸 무조건 뛰어야한다고 생각하면 중간에 1이 들어가면서 틀려먹는다.

그리고. 마지막 잔을 무조건 안마셔도 되잖아!

이거 점화식 진짜 어떻게 세우냐 .. 나중에..

점화식을 세워보자 ..

N = 1
DP[1] = Arr[1]

N=2
DP[2] = Arr[1] + Arr[2] 여기까지는 똑같지

N=3
DP[3] = Max ( Arr[1] + Arr[3] , Arr[2] + Arr[3] ) 뭐 이것도 비슷하다 3개연속으로 못먹으니까

N=4
DP[4] = Max( Arr[1] + Arr[2] + Arr[4], Arr[1] + Arr[3] + Arr[4], Arr[2] + Arr[4] ) 음 .. 그래

N일 경우
DP[N] = Max( DP[N-2] + Arr[N], DP[N-3] + Arr[N-1] + Arr[N], DP[N-1] )

DP[N-2] + Arr[N] 이랑 DP[N-3] + Arr[N-1] + Arr[N] 은 뭐 그렇다 쳐도!
DP[N-1]이 더 큰 경우가 있어 ?! .. 있더라

꼭 N번째 잔을 포함하지 않아도 되기 때문에 DP[N-1] 이 더 클 수도 있다고 한다.

100 100 1 100 100 1 이라고 하면 ..
400 이 딱봐도 정답인데, N을 무조건 포함해야 되면 301이나 그렇게 정답이 된다.

마지막 N을 무조건 선택하지 않아도 된다면 DP[N-1] 의 조건을 점화식에 꼭 써주자!

//
// Created by 신성준 on 2023/03/05.

//

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    int stair[10002] = {0,};
    int max_stair[10002] = {0,};
    cin >> N;
    for(int i = 1; i <= N; i++){
        cin >> stair[i];
    }

    for(int i = 1; i <= N; i++){
        if(i == 1){
            max_stair[1] = stair[1];
        }
        else if(i == 2){
            max_stair[2] = stair[1] + stair[2];
        }
        else{
            max_stair[i] = max(max_stair[i-3] + stair[i-1] + stair[i], max(max_stair[i-2] + stair[i], max_stair[i-1]));
        }
    }

    cout << max_stair[N];
}

어렵다 어려워. 나중에 꼭 다시보자