포도주 시식 C++ - 백준 2156

https://acmicpc.net/problem/2156

이 문제는 dp 문제이다.

이 문제가 계단오르기와 비슷해서 같은 방식으로
접근했다가 꽤 오래 잡고 있었던 문제이다.

(얍문님의 접근을 참고하였습니다.)

먼저 dp[i]에는 i번째까지의 포도주를 마셨을때의 최댓값을 담아야겠다고
생각했다.

하지만 항상 마신다는 접근하에 계속 틀렸다.

마시지 않는 경우도 생각해야했던 것이다.

i번째 포도주를 마시는 경우에는

1. i-2번째까지의 포도주의 최댓값 + i번째 포도주 값
2. i-3번째까지의 포도주의 최댓값 + i번째 포도주 값

i번째 포도주를 마시지 않는 경우에는

1. i-1번째까지의 포도주의 최댓값

이렇게 나누어 볼 수 있는데,
마시지 않는 경우를 생각하는 것이 중요했다.

코드는 다음과 같다.

#include <bits/stdc++.h>
#define MAX 10000+1
using namespace std;

int dp[MAX];
int arr[MAX];
int n;

int main(){
	ios_base :: sync_with_stdio(false); cin.tie(NULL);
	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(arr[0]+arr[1],max(arr[0],arr[1])+arr[2]);
	for(int i=3;i<n;i++){
		dp[i]=max(dp[i-2]+arr[i],max(dp[i-1],dp[i-3]+arr[i-1]+arr[i]));
	}
	cout << dp[n-1];
}