BOJ 2156번 포도주 시식

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

GitHub : https://github.com/junho0956/Algorithm/blob/master/2156/2156/%EC%86%8C%EC%8A%A4.cpp

 

dp[2] = max(dp[2],dp[1]) 을 안해주면서 WA을 2번이나받은 문제다

좀더 꼼꼼해지는 습관을 가지자..

 

포도주 시식은 연속3잔 이상을 마실 수 없을 때 주어진 양을 최대한 마실 수 있는 값을 구하는 문제이다.

생각해볼 부분은 이정도 인것 같다.

포도잔을 1,2,3,4,5,,, 이렇게 순서를 부여한다면

dp[0] = 1, dp[1] = 1+2 가 될 것이고

dp[2] 는 1+3, 2+3, ** 안마시는 경우인 dp[1] (=1+2) 가 될 것이다.

dp를 계산하는 반복문 안에는 이 조건을 줬음에도 초기값을 지정할때 이 조건을 안줘서..

 

dp[3] 부터는 3잔을 연속으로 마시지 않기 위해서 조건을 부여해주면 된다.

1. 현재잔을 마시는 경우

2. 현재잔을 마시지 않는 경우

이 2개로 나뉘게 된다.

 

1번을 통해 점화식을 유추해보자면

현재잔을 마시는 경우라면 현재잔-1 을 마실수 있지만 현재잔-2 을 마실수는 없다.

그러므로 1개의 점화식 arr[i]+arr[i-1]+dp[i-3] 을 유추해낼 수 있고

또 다른 경우는 현재잔-1을 마시지 않는다면 현재잔-2을 마실 수 있는 것이다.

이때 현재잔-2까지는 dp로 계산한 것이므로 arr[i]+dp[i-2] 을 유추해낼 수 있다.

2번과 함께 완성된 점화식을 보이면

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

dp[i] = max(dp[i], dp[i - 1]);

 

#include <iostream>
#include <algorithm>
using namespace std;
 
int dp[10000];
int arr[10000];
int n, Max;
 
int main() {
    ios::sync_with_stdio(false);
    
    cin >> n;
    for (int i = 0; i < n; i++) cin >> arr[i];
 
    dp[0] = arr[0], dp[1] = arr[0] + arr[1];
    dp[2] = max(dp[0] + arr[2], arr[1] + arr[2]);
    dp[2] = max(dp[2], dp[1]);
    for (int i = 3; i < n; i++) {
        dp[i] = max(arr[i] + arr[i - 1] + dp[i - 3], arr[i] + dp[i - 2]);
        dp[i] = max(dp[i], dp[i - 1]);
    }
    cout << dp[n-1];
    return 0;
}