다이나믹프로그래밍 - 백준 2156번 포도주 시식

www.acmicpc.net/problem/2156

2156번: 포도주 시식

IDEA

마실 수 있는 최대 포도주 양을 구하는 문제다. 

특히, 연속된 세개의 잔을 마실 수 없다라는 조건만 잘 맞춰주면 된다.

그래서 옛날에 계단 오르기를 풀었던 거처럼 똑같이 풀면 되는 거 아니야? 라고 생각했다.

그래서 dp[i] : i번째 포도주잔을 마셨을 때의 최대 포도주 양 을 저장해주고, 

 

• dp[i-2] + arr[i] : i-2번째 포도주잔을 마셨을 때의 최대 포도주 양  +  i번째 포도주잔의 양
  세번은 연속으로 마실 수 없기 때문에 i번째 잔과 i-2번째 잔을 마시는 방법이다. 
• dp[i-3] + arr[i-1] + arr[i] : i-3번째 포도주 잔을 마셨을 때의 최대 포도주 양 + i-1,i번째 포도주잔의 양
  마찬가지로 세번은 연속으로 마실 수 없기때문에 i번째와 그 직전 포도주를 마시려면 i-2번쨰는 마시면 안되므로 가장 가까운 포도주잔은 i-3번째가 된다.   

❌틀렸습니다❌가 뜬다 ㅜㅜ . 왜일까? 이런 경우를 생각해보자.

100 200 0 0 4 100 1같은 경우 최대 포도주를 마시려면 100 + 200 + 4 + 100 이어야한다. 

즉, 100을 기준으로 i-2번째 , i-3번째 모두 안마시는 경우도 있을 수 있다는 거다. 

그래서 하나의 경우를 더 추가해주어야한다. 

• dp[i-4] + arr[i-1] + arr[i] : i-2, i-3번째는 마시지 않는 경우 

그리고 추가로 하나 더 주의해야할 부분은 마지막 인덱스의 dp값이 최대가 아니라는 얘기이다. 

맨마지막 i번째를 택했을 때가 최대가 아닐수도 있는 것이다. 

 

Code

#include<iostream>
#include<algorithm>
using namespace std;

int arr[10001] = {0};
int dp[10001] = {0};

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &arr[i]);
	}
	dp[1] = arr[1];
	dp[2] = arr[1] + arr[2];
	dp[3] = max(arr[2]+arr[3] , dp[1] +arr[3]);
	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 - 4] + arr[i - 1] + arr[i] });
	}
	printf("%d", *max_element(dp, dp + n + 1));
}