2156 포도주 시식

계단오르기 문제와 비슷한 DP 문제이다.

계단 오르기와 비슷하게 기준을 만들어야 한다. 기준없이 경우를 고려하면 점화식을 세우기 힘들다.

포도주 잔의 갯수를 1 부터 시작하여 차례대로 dp를 만들어 나간다.

1잔일 경우 당연히 dp[1] = a[1]; 이다. dp[2] = a[1] + a[2]; 가 된다.

3잔 부터는 기준이 필요.

(3잔 이후로는 같은 원리가 적용됨)

*연속된 세잔은 불가능 하다.

1. 마지막 잔을 마시지 않을 경우   dp[n] = dp[n-1];   

2. 마지막 잔을 마시는데 첫 번째 잔일 경우.  dp[n] = dp[n-2] + a[n];

 

3. 마지막 잔을 마시는데 두 번째 잔일 경우. dp[n] = dp[n-3] + a[n-1] + a[n];

이렇게 경우를 나누어 주면 문제는 굉장히 쉽게 풀린다.

코드:

#include <iostream>

using namespace std;

int max(int a, int b, int c){

int tmp = a > b ? a : b;

return tmp > c ? tmp : c;

}

int main(){

int n;

int a[10001] = { 0, };

int dp[10001] = { 0, };

cin >> n;

for (int i = 1; i <= n; i++){

cin >> a[i];

}

dp[1] = a[1]; dp[2] = a[1] + a[2];

for (int i = 3; i <= n; i++){

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

}

cout << dp[n];

return 0;

}