[Algorithm]Baekjoon 2156번 : 포도주 시식

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

2156번: 포도주 시식

int wines[10001];
int dp[100001];
 
int maxNum(int a, int b, int c)
{
    return max(max(a, b), c);
}
 
int solution(int n)
{
    dp[1] = wines[1];
    dp[2] = wines[1] + wines[2];
 
    for (int i = 3; i <= n; i++)
    {
        dp[i] = maxNum(dp[i - 1], wines[i] + wines[i - 1] + dp[i - 3], wines[i] + dp[i-2]);
    }
 
    return dp[n];
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int num = 0;
    int temp = 0;
 
    cin >> num;
 
    for (int i = 1; i <= num; i++)
    {
        cin >> temp;
        wines[i] = temp;
    }
 
    cout << solution(num) << endl;
}

 

DP문제 많이 안풀어본 나에겐 바로 풀리지 않았던 문제.

거두절미하고 포도주를 맨마지막까지 마셨을때를 가정해서 생각해야한다.

여기서 dp[n]이 의미하는것은 n번째잔까지 왔을 때 최대로 마신 값이다.

마지막잔을 반드시 마실 필요가 없다. 3잔연속 못마신다는 조건상, n번째 잔을 안마시고 n-1,n-2번째 잔을 마시는 등 다른 경우의 수가 존재하기 때문이다.

 

이번문제같은 경우는, d[n]에 대해 3가지의 점화식이 나오고 그중 제일 높은값을 선택하면 된다.

3가지가 나오는 이유는 다음과 같다.

 

 1.마지막잔, 즉 n번째 잔을 마셨다고 가정하자. 그러면 여기서 또 두가지로 나뉜다.

바로 이전잔(n-1번째 잔)을 마셨느냐 안마셨느냐로 갈린다. 갈리는 이유는 3잔을 연속으로 못마신다는 조건 때문이다.

 

1-1. 바로 이전잔(n-1)을 마셨다면, n-2번째 잔은 마시면 안된다. 3잔연속이 되버리니까.

       그래서 건너뛰고 dp[n-3]을 더하면 된다. 

       -> wines[n] + wines[n-1] + dp[n-3]; 

 

1-2. 바로 이전잔(n-1)을 안마셨다면, 그냥 dp[n-2] 해버리면 된다.

       -> wines[n] + dp[n2]

 

2. 마지막잔, 즉 n번째 잔을 안마셨을때는 바로 이전까지의 제일 많이 마신값. 즉 dp[n-1]이 점화식이다.

      

즉, 특정 n번째에서 어떤값이 와도 상관 없을 때 최대값이 와야하는게 맞으므로(최대값을 구하는 문제이니까) 그 부분은 dp[n...n-1...등등]으로 점화식을 세우는것이다.

 

어쨌든 위와같이 dp[n]의 점화식은 총 3개가 나왔고, 이중에서 제일 큰값이 원하는 값이다.