백준 2156 - 포도주 시식

문제 번호: 2156

문제 제목: 포도주 시식

문제 주소: https://www.acmicpc.net/problem/2156

문제 내용

포도주 잔 n과 각 잔에 들어있는 포도주의 양이 주어질 때 최대로 마실 수 있는 포도주의 양을 출력한다.
단, 연속으로 놓여 있는 세 잔을 모두 마실 수는 없다.

테스트 케이스

6 6 10 13 9 8 1	33
6 8 2 0 0 2 8	20

문제 풀이

계단 오르기 문제와 비슷하지만 건너 뛰는 간격에 대한 제한이 없다는 차이가 있다. 즉, 2칸을 건너뛰지 않고 3칸을 건너뛸 수도 있다는 것.
이 때문에 점화식을 만든 후 값을 구하는 것은 계단오르기와 동일하나 dp[i - 2]와 dp[i-3]만 알면 되었던 계단오르기와 달리, dp[i - 3] 대신 dp[0] ~ dp[i - 3] 중에서 가장 큰 값을 알아야 한다. dp 중에서 가장 큰 값을 저장하는 변수를 만들고 새로운 dp 값을 구할 때마다 이 변수에 가장 큰 값을 입력해두는 식으로 진행하면 최대로 마실 수 있는 포도주의 양을 구할 수 있다.

풀이 코드

#include <iostream>
using namespace std;

void BAEKJOON_2156()
{
	int n;
	cin >> n;
	uint32_t max;
	if (n == 1)
	{
		cin >> max;
	}
	else
	{
		/*----------배열 할당 및 값 입력-----*/
		uint32_t* pt = new uint32_t[n + 1];
		uint32_t* dp = new uint32_t[n + 1];
		pt[0] = 0;
		for (int i = 1; i <= n; i++)
		{
			cin >> pt[i];
		}
		/*---------점화식-------------------*/
		dp[0] = 0;
		dp[1] = pt[1];
		dp[2] = pt[1] + pt[2];
		max = dp[2] > dp[1] ? dp[2] : dp[1];
		uint32_t semiMax = 0;
		/*---------값 구하기----------------*/
		for (int i = 3; i <= n; i++)
		{
			semiMax = dp[i - 3] > semiMax ? dp[i - 3] : semiMax;
			uint32_t before = dp[i - 2] + pt[i];
			uint32_t other = semiMax + pt[i - 1] + pt[i];
			dp[i] = before > other ? before : other;
			if (dp[i] > max)
			{
				max = dp[i];
			}
		}
		/*----------배열 할당 해제----------*/
		delete[] pt;
		delete[] dp;
	}
	cout << max << endl;
	return;
}