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

---

0. 문제

 

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

 

1. 아이디어

 

1) top-down 방식으로 풀기로 했다!

 

2) 지금 포도주 잔을 마시기 전에, 1. 이전 잔을 마시지 않았다 2. 연속해서 1잔 마셨을 때 3. 연속해서 2잔 마셨을 때 경우를 구분하고, 함수의 매개변수로 받는다.

 

2. 소스코드

 

#include <iostream>
#include <algorithm>
int N, value[10000], dp[10000][3];
//value 배열은 포도주의 양을 저장
//dp 배열은 DP방식으로 문제를 풀기 위해 이전까지의 값들을 저장
 
int drink(int idx, int c)
{
    if (idx == N) return 0; // 0열부터 N-1열까지가 유효
    if (dp[idx][c] != -1) return dp[idx][c];
    //dp[idx][c]에 값이 있다는 것은 이전에 계산한 적이 있음!
 
    int result = drink(idx + 1, 0);
 
    if (c == 0) result = std::max(result, drink(idx + 1, 1) + value[idx]);
    if (c == 1) result = std::max(result, drink(idx + 1, 2) + value[idx]);
 
    dp[idx][c] = result;
    return result;
}
 
int main()
{
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cin >> N;
    for (int i = 0; i < N; i++)
    {
        std::cin >> value[i];
        for (int j = 0; j < 3; j++)
            dp[i][j] = -1;
    }
    std::cout << drink(0, 0);
}

 

3. 결과

 

 

4. 피드백

 

• 아직 탑다운은 머리가 빙빙 돈다.. 일부러라도 연습을 해야겠다.

• 필요한 정보들을 잘 사용하자 (예를 들어 이번 문제의 경우에는 함수 매개변수 c !!)

---