알고리즘 :: 백준 :: DP :: 2156:: 포도주 시식

문제

문제링크

1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오. 단, 연속해서 3잔 마실 수 없다.

문제접근

• n이 10,000까지라 억지로 bruteforce로 풀 수는 있다.
• DP로 풀겠다고 마음먹었다면 직접 예제에 대해 그림을 그려보는 것이 좋은 출발점이다.
• 
• 
• 
• 
• 따라서 점화식을 세워보면,
  $D(n) = MAX(D(n-1), D(n-2) + a(n), D(n-3)+a(n-1)+a(n))$

코드

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

int n, a[10001], dp[10001];
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(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] << '\n';	
}

결과