BOJ 2156: 포도주 시식

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

---

알고리즘 분류 | 동적 계획법 (Dynamic Programming, DP)

풀이 | 

대표적인 DP 문제라고 한다.

연속으로 포도주를 3잔 마실 수 없다는 것이 조건이다. 즉, 연속으로 포도주를 두 잔까지만 마실 수 있다.

n번째 포도주를 기준으로 연속을 생각했을 때
1. n번째 포도주를 연속으로 첫 번째 마시는 경우
2. n번째 포도주를 연속으로 두 번째 마시는 경우
3. n-1번째 포도주를 연속으로 두 번째 마셔서 n번째 포도주를 마실 수 없는 경우

이렇게 세 경우가 있다. 그림으로 표현하면 다음과 같다.

두 잔 다 연속으로 마시지 않는 경우는 최댓값을 구하는 문제 특성상 고려할 필요가 없다.

위의 세 경우로 점화식을 세워보았다.
dp[n] = dp[n-2] + num[n]
dp[n] = dp[n-3] + num[n-1] + num[n]
dp[n] = dp[n-1]

점화식에 n-3까지 포함되기 때문에 반복문의 시작은 3으로 했고,
dp[1], dp[2]를 초기화해주었다.

소스 코드 |

#include <iostream>
using namespace std;
int num[10001];
int dp[10001];
#define max(a, b) ((a > b) ? a : b)

int main(void) {
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> num[i];
	}

	dp[1] = num[1];
	dp[2] = num[1] + num[2];
	
	for (int i = 3; i <= n; i++) {
		dp[i] = max(dp[i - 3] + num[i-1] + num[i], dp[i - 2] + num[i]);
		dp[i] = max(dp[i], dp[i - 1]);
	}
	cout << dp[n] << '\n';

	return 0;
}