백준 2156 (포도주 시식) / C++

문제 링크 : www.acmicpc.net/problem/2156

2156번: 포도주 시식

> 풀이

 

0부터 n까지 차근차근 쌓아가는 dp를 통해 구현했습니다. dp[n] = n번째 와인까지 마시는 최대의 경우

 

따라서 n 번째 잔에서 이전 잔을 마시느냐 안마시느냐 두 가지 경우의 최대를 구하는 방식을 생각했는데, 

 

이렇게 구현하니 dp[n - 1]를 비교하지 못하더라구요. 두가지 경우의 최대를 구한 후, n - 1번째와 비교하여 n번째 잔을 마시는게 나은지, 차라리 안마시는게 나은지 비교하는게 ( max dp[i], dp[i - 1]; ) 필요했습니다.

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

int N, dp[10001], wine[10001];

int main(void) {
        scanf("%d", &N);
        for(int i = 1; i <= N; i++) scanf("%d", &wine[i]);
        dp[1] = wine[1];
        dp[2] = wine[1] + wine[2];

        for (int i = 3; i <= N; i++) {
                dp[i] = wine[i] + max(dp[i - 2], wine[i - 1] + dp[i - 3]);
                dp[i] = max(dp[i], dp[i - 1]);
        }

        printf("%d", dp[N]);
}