[백준] 2156번: 포도주 시식 풀이 및 해설(C++)

문제 이미지

풀이

포도주를 먹어서 얻는 값은 모두 양수이다. 즉, 무조건 먹을 수 있으면 먹는게 이득이다.

입력값들을 arr[]에 저장한다. 그리고 동적계획법을 위한 dp[]를 만든다.

dp[n]은 n번째 잔을 마지막으로 먹었을 때 가지는 최대의 점수 값이다.

하지만 n-2,n-1번째 잔까지 모두 먹은 경우는 n번째 잔을 먹을 수 없다.

 

즉 이번에 먹는 잔이

1.(n-2번째 잔은 먹지 않은 상태) AND (n-1번째 잔은 먹은 상태) 거나

2.(n-2번째 잔은 먹은 상태) AND (n-1번째 잔은 먹지 않은 상태) 여야 한다.

 

둘다 먹지 않은 상태는 위에서 쓴데로, 무조건 먹는게 이득이라고 했으니 생각하지 않는다.

 

즉 1번 식은 n-3번째까지 먹었을 경우의 최댓값에 n-1번째 잔과 n번째 잔을 더하고

2번 식은 n-2번째까지 먹었을 경우의 최댓값에 n번째 잔을 더한다.

 

1번을 식으로 표현하면 dp[n]=dp[n-3]+arr[n-1]+arr[n] 

2번을 식으로 표현하면 dp[n]=dp[n-2]+arr[n] 이다.

 

이중 큰것을 취하면 된다.

 

즉, dp[n]=max(dp[n-3]+arr[n-1]+arr[n],dp[n-2]+arr[n])이다.

 

 

 

 

 

 

 

 

 

 

 

라고, 생각했다가 틀렸다...

 

어떤 경우를 생각하지 못한 것일까?

 

이 문제는 2579번 계단 오르기 문제와 아주 유사하다.

2023.06.09 - [algorithm/dp] - [백준] 2579번: 계단 오르기 풀이 및 해설(C++)

[백준] 2579번: 계단 오르기 풀이 및 해설(C++)

 

그리고 그 문제에서는 dp[n]=max(dp[n-3]+arr[n-1]+arr[n],dp[n-2]+arr[n]) 으로 풀어서 맞았다.

 

그럼 이 문제와 그 문제는 무엇이 다른 것일까?

 

계단 오르기 문제는 2단 점프가 되지 않았다.

하지만 이 문제는 몇번을 점프해도 상관이 없다.

 

계단 오르기 문제는 끝 지점이 정해져 있다.

하지만 이 문제는 끝에 오는 값을 취하지 않아도 된다.

 

 

예시 배열로 2,2,1,1,2,2 가 들어온다고 해보자

최댓값은 2만 택한 8이지만, 이 알고리즘 상으로는 2단점프가 안되기 때문에 7이 나온다.

지금 먹지 않고, 미래에 2잔을 더 마시는 게 더 큰값을 가져오게 할 수 도 있다. 

 

따라서 2개 연속으로 먹지 않았을 때도 고려해야 한다.

 

몇번을 점프해도 상관없다고 했지만 3연속 이상을 고려하지 않는 이유는 3연속 점프 시 xxx로 점프하지 말고 xox 로 점프한 가운데 하나를 마시는 것이 더 큰값이 되기 때문이다.

 

그리고 이 문제에서는 꼭 끝값을 취하지 않아도 된다.

즉,  n번째 잔을 먹지 않고도 최댓값이 올 수 있음을 알아야 한다.

 

따라서 2단점프를 고려했을 시 dp[n-1]과 dp[n] 중 최댓값이 나온다.

dp[n-2]는 dp[n-2]+arr[n] 이 무조건 더 크다는 반례가 있기에 생각하지 않는다.

 

 

 

따라서 점화식은 dp[n]=max(dp[n-3]+arr[n-1]+arr[n],dp[n-2]+arr[n],dp[n-1])이 된다.

 

 

해답 코드

#include <iostream>
#include <algorithm>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;


int main(){
    fastio;
    int n;
    long long stair[10001];
    long long dp[10001];
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>stair[i];
    }
    dp[0]=stair[0];
    if(n==1){
        cout<<dp[0];
        return 0;
    }
    dp[1]=stair[0]+stair[1];
    if(n==2){
        cout<<dp[1];
        return 0;
    }
    dp[2]=max({stair[0]+stair[1],stair[0]+stair[2],stair[1]+stair[2]});
    for(int i=3; i<n; i++){
        dp[i]=max(dp[i-3]+stair[i]+stair[i-1],dp[i-2]+stair[i]);
        dp[i]=max(dp[i-1],dp[i]);    
        
    }
   
    cout<<dp[n-1];
    return 0;
    

}

해맸던 부분

위에서 쓴데로 dp[n-1] 을 고려하지 못해 해맸다... 계단수열이나 지금까지 나왔던 다른 dp문제와는 어떤 점이 다른지 알아보아야 겠다.