백준 2156 - 포도주 시식

문제

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

2156번: 포도주 시식

 

풀이

세 가지 포도주를 연속적으로 선택할 수 없으므로 n 번째에서 선택을 세 가지 경우로 나눈다. 

0이면 포도주를 선택 하지 않는 경우,

1이면 포도주를 1번 연속 선택한 (n) 경우,

2이면 포도주를 2번 연속 선택한 (n - 1, n) 경우로 나눈다.

n 번째에서 세 가지 경우 중 가장 큰 값으로 선택을 하면 된다.

 

arr[n] = n번째 포도주 양, dp[n][state] = n번째 포도주잔과 state(0, 1, 2) 라고 하면 다음의 점화식을 구할 수 있다.

dp[n][0] = max{

  dp[n-1][0],

  dp[n-1][1],

  dp[n-1[2]

}

dp[n][1] = dp[n - 1][0] + arr[n]

dp[n][2] = dp[n - 1][1] + arr[n]

 

세 가지 경우 중 최댓값을 찾으면 된다.

 

코드

탑다운 방식

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int n;
int arr[10001];
int dp[10001][3];
int result;
 
// 2: 2번 연속 선택,  1: 1번 연속 선택, 0: 선택 X
int f(int n, int state)
{
    if (n <= 0) return 0;
    if (dp[n][state]) return dp[n][state];
 
    if (state == 0) return dp[n][state] = max(f(n - 1, 0), max(f(n - 1, 1), f(n - 1, 2)));
    else if (state == 1) return dp[n][state] = f(n - 1, 0) + arr[n];
    else return dp[n][state] = f(n - 1, 1) + arr[n];
}
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    cin >> n;
 
    for (int i = 1; i <= n; i++) cin >> arr[i];
 
    result = max(f(n, 0), max(f(n, 1), f(n, 2))); 
 
    cout << result;
 
    return 0;
}
 

 

바텀업 방식

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int n;
int arr[10001];
int dp[10001][3];
int result;
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    cin >> n;
 
    for (int i = 1; i <= n; i++) cin >> arr[i];
 
    dp[1][0] = 0; dp[1][1] = arr[1]; dp[1][2] = 0;
    for (int i = 2; i <= n; i++)
    {
        dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][1], dp[i - 1][2]));
        dp[i][1] = dp[i - 1][0] + arr[i];
        dp[i][2] = dp[i - 1][1] + arr[i];
    }
 
    result = max(dp[n][0], max(dp[n][1], dp[n][2]));
    cout << result;
 
    return 0;
}