백준 02156 - 포도주 시식

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

2156번: 포도주 시식

 

고려사항

- i 번째 포도주를 안마신다면, i-1번째 포도주를 안마심(0), 마셨는데 연속 1잔째임(1), 마셨는데 연속 2잔째임(2) 를 나타내는

memo[i-1][0~2] 중 최대값을 계산해야 함.

- 재귀로 구현했더니 몇몇 테스트 케이스에서 답이 안구해짐...

아마도 아까 언급한, 안 마셨을 때의 값이 이전 인덱스의 모든 값중 최대값을 구해야하는데,

재귀로 할 경우 반복문으로 구하는 경우와 달리 memo[i-1][2] 가 호출되기 전에 memo[i-2][cnt] 가 호출되어

초기값인 -1 로 계산이 되어서 그런것 같음..!

 

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;

int n, ans = -1;
int wine[10001];
int memo[10001][3];

void dp(){
    memo[1][0] = 0;
    memo[1][1] = wine[1];
    memo[1][2] = -1;

    memo[2][0] = wine[1];
    memo[2][1] = wine[2];
    memo[2][2] = wine[1] + wine[2];

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

    ans = max( memo[n][0], max(memo[n][1], memo[n][2]));
    return;
}

int main(){
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>wine[i];
    }
    memset(memo,-1,10001*3*4);

    dp();
    cout<<ans;
    return 0;
}