[백준(BOJ)] 2156번: 포도주 시식 (Dynamic Programming, C++)

📝 문제풀이 과정

---

i번째 마시는 경우

• i-1번째 마시는 경우: DP[i] = G[i] + G[i-1] + DP[i-3]

• i-1번째 안 마시는 경우: DP[i] = G[i] + DP[i-2]

i번째 안 마시는 경우

• DP[i] = DP[i-1]

 

• 최종 DP[i]는 i번째 마시는 경우의 DP[i]와 i번째 안 마시는 경우의 DP[i-1]에서 max로 저장한다.

• DP[0], DP][1] 초기값을 구해줘야 한다.

  • DP[0]인 경우에는 이전이 없으므로 G[0] 넣어주고, 그렇지 않은 경우엔 현재와 이전 포도주 양을 넣어준다.

 

💻 C++ 제출코드

---

#include <stdio.h>
#include <algorithm>

using namespace std;

int main(){
    int n;
    scanf("%d", &n);
    int G[n] = {0};
    int DP[n] = {0};

    for(int i=0; i<n; i++) scanf("%d", &G[i]);
    for(int i=0; i<2; i++){
        if(i==0) DP[i] = G[i];
        else DP[i] = G[i] + G[i-1];
    }
    for(int i=2; i<n; i++){
        DP[i] = max(G[i] + G[i-1] + DP[i-3], G[i] + DP[i-2]);
        DP[i] = max(DP[i-1], DP[i]);
    }

    printf("%d", DP[n-1]);
}

 

👏 결과

---