[백준 2156][C++] 포도주 시식 (Silver 1)

[문제보기]

 2156. 포도주 시식

2156번: 포도주 시식

 

[풀이과정]

이 문제는 저번에 풀었던 계단 오르기 문제랑 비슷한 형태를 띠고 있는 문제이다.

하지만 계단 오르기와 다른 점은 조건에 맞춰 선택을 할 수 있다는 점이다. 

선택을 할 수 있다는 것은 내가 한번 안 먹을 경우와, 두 번 연속 안 먹을 경우가 있다는 뜻이다.

예를 들어 100, 400, 2, 1, 4, 200 이 주어졌을 때,

첫 번째, 두 번째를 선택 후 세, 네 번째 포도주는 건너뛰고, 다섯 번째, 여섯 번째 포도주를 선택하는 경우가

포도주를 제일 많이 먹을 수 있는 경우가 된다.

 

따라서 점화식으로는 

dp[i] = max(dp[i-3]+arr[i-1]+arr[i], dp[i-2]+arr[i]); 를 하고

dp[i] = max(dp[i-1], dp[i]); 식을 한번 더 검사를 해줘야 된다.

 

[소스코드]

#include <iostream>
using namespace std;

int main(){
    int dp[10001] = {0};
    int arr[10001] = {0};

    int n;
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> arr[i];
    }

    dp[1] = arr[1];
    dp[2] = arr[1]+arr[2];
    int Max = dp[2];
    for(int i=3; i<=n; i++){
        dp[i] = max(dp[i-3]+arr[i-1]+arr[i], dp[i-2] + arr[i]);
        dp[i] = max(dp[i], dp[i-1]);
        Max = max(Max, dp[i]);
    }
    
    cout << Max;
}

 

[해결 과정 중 실수한 부분]

처음 문제를 읽고 계단 오르기와 비슷한 문제로 코드를 짠 거까지는 빨랐지만, 계속 틀리게 나와

반례를 찾아서 확인을 해보니 두 번 연속을 건너뛰는 경우를 생각 안 해줬었다.