[백준][2156번][DP] 포도주 시식

포도주 시식

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

<코드>

#include <stdio.h>
 
int max(int a, int b){
    return a > b ? a : b;
}
 
int main(void){
 
    int N;
    int wine[10010] = {};
    int Dp[10010] = {};
    scanf("%d", &N);
 
    for (int i = 1; i <= N; i++)
        scanf("%d", &wine[i]);
 
    for (int i = 1; i < 3 && i <= N; i++){
        if (i == 1)
            Dp[i] = wine[i];
        else
            Dp[i] = wine[i] + wine[i - 1];
    }
 
    for (int i = 3; i <= N; i++){
        int result = 0;
        result = max(wine[i] + Dp[i - 2], Dp[i - 1]);
        result = max(result, wine[i] + wine[i - 1] + Dp[i - 3]);
        Dp[i] = result;
    }
    
    printf("%d\n", Dp[N]);
}

<문제 푼 요령>

1. 이 문제 같은경우는 포도주를 세개를 연속을 먹을 수없다는 것을 고려해서 메모라이션 하면 된다.

2. 즉 현재 먹는 포도주의 합이 최대일 경우를 생각해보면 

- 내가 현재의 포도주를 먹지 않았을 경우와

- 현재의 포도주를 마시고 이전꺼를 안마실 경우

- 현재의 포도주와 이전의 포도주를 마신 경우

3. 이렇게 3개의 경우를 따져서 저장해 주면 된다. 즉

- Dp[i-1] : 내가 현재의 포도주를 먹지 않았을 경우와

- wine[i] + Dp[i-2] : 현재의 포도주를 마시고 이전꺼를 안마실 경우

- wine[i] + wine[i-1] + Dp[i-3] :현재의 포도주와 이전의 포도주를 마신 경우

4. 저 3개의 값만 비교하면 최대값을 구할 수 있다.