[백준 DP] 2156번 - 포도주 시식

2156번 - 포도주 시식 

 

<문제>

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

2156번: 포도주 시식

 

<문제 풀이>

arr[] -> 문제에서 입력 받은 포도주의 용량을 저장

dp[][] -> 선택한 포도주 잔의 용량의 합을 저장 

점화식
dp[0][i] = max(dp[1][i-1], dp[2][i-1]) + arr[i]
dp[1][i] = max(dp[0][i-2], dp[1][i-2], dp[2][i-2]) + arr[i]
dp[2][i] = max(dp[0][i-3], dp[1][i-3], dp[2][i-3]) + arr[i]

 

<코드>

#include <iostream>
#include <algorithm>
#define MAX 10001
using namespace std;

int T;
int arr[MAX];
int dp[3][MAX];
int m0, m1, m2;


int maxSum() {

	for (int i = 2; i <= T; i++) {
		dp[0][i] += max(dp[1][i - 1], dp[2][i - 1]) + arr[i];
		dp[1][i] += max({ dp[0][i - 2], dp[1][i - 2], dp[2][i - 2] }) + arr[i];
		dp[2][i] += max({ dp[0][i - 3], dp[1][i - 3], dp[2][i - 3] }) + arr[i];
	}

	int size = sizeof(arr) / sizeof(*arr);
	for (int i = 1; i <= T; i++) {
		m0 = *max_element(dp[0], dp[0] + size);
		m1 = *max_element(dp[1], dp[1] + size);
		m2 = *max_element(dp[2], dp[2] + size);
	}

	return max({ m0, m1, m2 });
}

int main() {
	cin >> T;

	for (int i = 1; i <= T; i++) {
		cin >> arr[i];
		if (i == 1) {
			dp[0][i] = arr[i]; dp[1][i] = arr[i]; dp[2][i] = arr[i];
		}
	}

	cout << maxSum() << endl;
	return 0;
}

 

<결과>

 

 

2022.12.18