[C++/Python] 백준 2156 - 포도주 시식

문제 링크

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

2156번: 포도주 시식

 

 

N이 2일 때는 와인의 첫번째와 두번째 값을 더한 값입니다. 

N이 3이상일 때는 위와 같이 연속되는 값이 3개가 넘지않는 경우 중

총 3가지의 값 중 최대값이 정답이 됩니다.

 

 

구현 코드

 

	#include <iostream>
	#include <algorithm>
	#define endl '\n'
	#define fastio cin.sync_with_stdio(false); cin.tie(nullptr)
	using namespace std;
	const int MAX = 10001;
	int wine[MAX];
	int dp[MAX];
	int main(){
	fastio;
	int n;
	cin >> n;
	for(int i=1;i<=n;i++)
	cin >> wine[i];
	dp[1] = wine[1];
	dp[2] = wine[1] + wine[2];
	for(int i=3;i<=n;i++){
	dp[i] = max(dp[i-1],dp[i-3]+wine[i-1]+wine[i]);
	dp[i] = max(dp[i],dp[i-2]+wine[i]);
	}
	cout << dp[n] << endl;
	return 0;
	}

view raw 2156.cpp hosted with ❤ by GitHub

	n = int(input())
	wine = []
	wine.append(0)
	for _ in range(n):
	wine.append(int(input()))
	dp = []
	dp.append(0)
	dp.append(wine[1])
	if(n>1):
	dp.append(wine[1] + wine[2])
	for i in range(3,n+1):
	dp.append(max(dp[i-1], dp[i-2] + wine[i], dp[i-3] + wine[i-1] + wine[i]))
	print(dp[n])

view raw 2156.py hosted with ❤ by GitHub