백준 2156번 - 포도주 시식

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

이 문제는 5개월 전에 풀 때, 3개월 전에 풀 때, 그리고 지금 다시 풀 때 항상 틀린 문제다.
정답률이 34%에 이르는데 정답률이 비슷한 다른 문제보다 체감 난이가 더욱 높게 느껴졌다.
막상 다 풀고나면 그닥 어려운 느낌은 아닌데 중간에 생각하지 못한 까다로운 부분이 있어서 항상 풀때마다 실수하고 틀렸던 것 같다. 

물론 알고리즘을 잘하는 사람들에게는 굉장히 쉬운 문제로 보여서....평소에 알고리즘 공부를 더 열심히 해야겠다고 생각나게 하는 문제이다...


본론으로 들어가서 

우선 n값이 1부터 10000사이의 값을 보고 10000을 제곱하게 되버리면 바로 시간초과가 나게 된다.

dp로 접근할 때 점화식을 어떻게 세우냐에 따라서 여러가지 답이 나올 수 있다. 

그리고 처음에 어떻게 점화식을 세워서 접근할 것인지가 제일 중요한 문제이다. 


n번째 포도주를 선택해서 마시는 경우 직전에 마신 포도주가 n-1번째 인 경우, n-2번째인 경우로 문제에 접근할 수 있다. 

또는 1번 연속 마시는 경우, 2번 연속 마시는 경우와 같이 점화식을 세울 수도있다. 

사실 두 접근법은 크게 차이가 나지는 않지만 실제로 구현할 때 배열 원소를 조금 다르게 해줘야 하는 차이가 있다. 

중요한건 점화식을 세운 다음에 이와 관련해서 접근하는 것이고 나는 두 번째 방식으로 문제에 접근했다.



우선 점화식은 다음과 같다.
dp[1][n] = n번째 포도주를 1번 연속 마셨을 때의 최대 값 (n-1번째는 마시지 않음)
dp[2][n] = n번째 포도주를 2번 연속 마셨을 때의 최대 값 (n-1번째 마시고 바로 n번째를 마시는 경우)


dp[2][n]의 경우에는 2번 연속 마신 경우이기 때문에 n번째 포도주의 값에다가 바로 dp[1][n-1]을 더해주면 된다. 


그런데 문제는 dp[1][n]의 점화식이다.
dp[1][n]=max(dp[1][n-2],dp[2][n-2])+n번째 포도주
위와 같이 점화식을 세우고 고민하다가 바로 n-3번째를 고려하지 않았을 경우에 반례를 생각하게 됐다.


5개의 포도주가 있다고 가정하고 그 값을 각각 "20", "10", "9", "1", "2" 라고 생각해보자


여기서 5번째에서 위의 dp 점화식을 적용하면 3번째의 최대값을 고려해야 하고 3번째에서 나올 수 있는 최대값은 20과 9를 더한 29일 것이다.
그러나 2번째 원소까지 고려한다면 20과 10을 더한 30이 최대값이고 결론적으로는 n-2번째보다 n-3번째의 포도주의 최대값이 더 큰 값이 될것이다.
만약에 n-4번째 까지 가게 된다면, 이미 n-1번째와 n-2번째에서 각각의 점화식에 맞게 최대값을 구한 것이기 때문에 n번째에서는 n-3번째까지 고려하면 된다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main(){
    int n,ans=0;
    cin>>n;
    
    vector<int> vec(n+1,0);
    for(int i=1;i<=n;i++)
        scanf("%d",&vec[i]);
    
    vector<vector<int>> dp(3,vector<int> (n+1,0));
    
    dp[1][1]=dp[2][1]=vec[1];
    dp[1][2]=vec[2], dp[2][2]=vec[1]+vec[2];
    ans=(n==1)? vec[1]:vec[1]+vec[2]; //n이 1이거나 2일 경우
    
    for(int i=3;i<=n;i++){
        dp[1][i]=max(max(dp[1][i-3],dp[2][i-3]),max(dp[1][i-2],dp[2][i-2]))+vec[i];
        dp[2][i]=dp[1][i-1]+vec[i];
        
        ans=max(ans,max(dp[1][i],dp[2][i]));
    }
    cout<<ans<<endl;
}