[C] 2156: 포도주 시식

처음에 점화식을 쉽게 찾았고 구현도 다른 DP 문제처럼 쉽게 되서 완전 쉽게 풀줄 알았다...

점화식은 쉽게 보면 

 

근데 여기서 간과한 점이 다른 "계단 오르기"문제와의 차이점이 있다는 것인데

그건 바로 와인을 안마셔도 된다는 것이었다..!

 

예를 들어 (6) 100 100 1 1 100 100의 최대 포도주 양은 계단 오르기 문제에서는 301이지만 여기서는 400이 된다.

3번째와 4번째에서는 안마시는게 이득이다.

따라서 if(dp[i]<dp[i-1]) 일때는 dp[i]=dp[i-1]라는 조건을 추가해줘야한다.

 

그리고 난 cnt라는 변수를 써서 몇번째 연속으로 마시지는지 확인했는데

다른 방법이 있는 것 같기도 하다(?)

 

너무 생각없이 dp문제인 것을 확인하고 기계적으로 푼 것 같다.

좀 더 정확하고 천천히 예외를 생각하면서 풀어야겠다는 생각이 들었다.

 

#include <stdio.h>

int dp[10002];
  int main(void)
  {
    int n,cnt;
    scanf("%d", &n);
    int arr[n+1];
    for(int i=1;i<n+1;i++)
      {
        scanf("%d",&arr[i]);
      }
    int max;
    if(n>=1){
       dp[1]=arr[1];
      max=dp[1];
    }   

    if(n>=2)
    {
      dp[2]=dp[1]+arr[2];
      cnt=2; //연속 두잔을 마심
      max=dp[2];
    }   

    if(n==3)
    {
      if(arr[2]>arr[1])
         dp[3]=arr[2]+arr[3];           
      else
      {
        dp[3]=arr[1]+arr[3];
        cnt=1;
      }
      max=dp[3];
      if(arr[1]+arr[2]>max)
      {
        max=arr[1]+arr[2];
        cnt=0;
      }
    }


    
    
    for(int i=3;i<=n;i++)
      {
        if(arr[i]==0) //음이 아닌 정수였음! 선택안하는게 제일 이득임
        {
          dp[i]=dp[i-1];
          cnt=0;
        }
        if(cnt==2)
        {
          if(arr[i-1]+dp[i-3]>dp[i-2]) //이 경우 점화식이 달라짐!! 이걸 찾는게 중요
          {
            dp[i]=arr[i]+arr[i-1]+dp[i-3];
            cnt=2; //2개가 연속됨
          }
          else
          {
            dp[i]=dp[i-2]+arr[i];
            cnt=1; //하나를 건너뛰어 마시기 떄문에 연속되는 잔이 1이 됨
          }
        }
        else  //cnt==1 , 0
        {
          if(dp[i-1]>dp[i-2]) //
          {
            dp[i]=dp[i-1]+arr[i];
            cnt=2; //연속되는 두 잔을 마심
          }
          else
          {
            dp[i]=dp[i-2]+arr[i];
            cnt=1; //1로 유지됨
          }          
        }
        
        if(dp[i]<dp[i-1])
        {
          dp[i]=dp[i-1];
          cnt=0; //그냥 선택을 안함
        }
           
      }
    if(n>3)
      max=dp[n]>dp[n-1]?dp[n]:dp[n-1]; //max가 될 수 있는 곳은 맨 끝이거나 끝에서 두번째임

  /* for(int i=1;i<=n;i++)
      printf("%d ",dp[i]);
    printf("\n");   */
    printf("%d",max);
    
  }