[백준/C++] 2156번_포도주 시식

문제는 다음과 같습니다.

저는 먼저 배열 a[n]와 2차원 배열 dp[n][i]를 이용하였습니다.
배열 a[n]에는 n번째 포도주의 양을 넣었고,

핵심인 배열은 dp[n][i] 입니다.

dp[n][0]: n번째까지 왔을 때, n번째에서 포도주 시식 x

dp[n][1]: n번째까지 왔을 때, n번째에서 포도주 시식 o

그래서 n번째까지 왔을 때, 최대는 max(dp[n][0], dp[n][1])이 됩니다.

그리고 각각의 dp[n][0], dp[n][1]을 구하는 과정은 다음과 같습니다.

dp[n][0] = max(dp[n-1][0], dp[n-1][1])

dp[n][1] = max(dp[n-2][0]+a[n-1], dp[n-1][0])+a[n]

제가 직접 써서 푼 풀이도 같이 첨부하겠습니다.

전체 코드는 다음과 같습니다.

#include <bits/stdc++.h>
using namespace std;


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    long long dp[10001][2]={0, };
    long long a[10001]={0, };
    int n, tmp;
    cin>>n>>tmp;
    a[1]=tmp; dp[1][0]=0; dp[1][1]=tmp;
    cin>>tmp;
    a[2]=tmp; dp[2][0]=a[1]; dp[2][1]=(a[1]+tmp);

    for(int i=3; i<=n; i++){
      cin>>tmp;
      a[i]=tmp;

      dp[i][0]=max(dp[i-1][0], dp[i-1][1]);
      dp[i][1]=max(dp[i-2][0]+a[i-1], dp[i-1][0])+tmp;
    }

    long long res = max(dp[n][0], dp[n][1]);
    cout<<res<<"\n";
    return 0;
}