[c++] 백준 2156 포도주 시식

백준 단계별로 풀어보기 [동적계획법 1] 포도주 시식

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

2156번: 포도주 시식

 

[풀이]

이전에 했던 계단오르기와 매우 유사한 동적프로그래밍 문제이다. 따라서 3번 연속 포도주를 마시면 안되기 때문에 다음과 같은 점화식이 도출된다.

1. max[n] = max[n-2] + juice[n]

2. max[n] = max[n-3] + juice[n-1] + juice[n]

다만 계단 오르기 문제와 다르게 유의해야 할 점은 마지막 계단을 무조건 밟아야했던 이전 문제와 달리 포도주 시식 문제에는 마지막 포도주를 꼭 마셔야한다는 조건이 없다는 것이다. 마지막 계단을 밟아야한다는 것은 마지막 계단에 대한 경우의 수들의 누적합 중 가장 큰 값을 구해야함을 의미했다. 따라서 마지막 값 이전의 값이 최대여도 배제해야했다. 하지만 이번 문제에는 그런 조건이 없으므로 n번째 포도주를 마시지 않는다면 n-1번째 잔까지 왔을 때 마실 수 있는 최대 포도주의 양이 답이 될 것이다. 즉, 연속으로 포도주를 마시지 않는 경우를 고려해주어야 한다. 따라서 다음의 식이 추가된다.

3. max[n] = max(max[n], max[n-1])

 

[코드]

#include <iostream>
#include <algorithm>

int juice[10001];
int max[10001];

int main() {
	int n;//포도주 잔
	std::cin >> n;
	for (int i = 1; i <= n; i++)
		std::cin >> juice[i];

	max[0] = 0;
	max[1] = juice[1];
	max[2] = max[1] + juice[2];

	for (int i = 3; i <= n; i++) {
		max[i] = std::max(max[i - 3] + juice[i - 1] + juice[i], max[i - 2] + juice[i]);
		max[i] = std::max(max[i], max[i - 1]);
	}

	std::cout << max[n];

}