BOJ_2156_포도주 시식

문제 이름 : 포도주 시식 (2156번)

문제 유형 : DP (DynamicProgramming, 다이나믹프로그래밍)

작성 언어 : C++

 

문제

효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오. 

예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.

입력

첫째 줄에 포도주 잔의 개수 n이 주어진다. (1≤n≤10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다.

출력

첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력한다.

예제 입력 1

6
6
10
13
9
8
1

예제 출력 1

33

 

 

풀이

2021.07.15 - [알고리즘] - BOJ_2579_계단 오르기

BOJ_2579_계단 오르기

앞에서 풀었던 문제와 비슷하다.

DP 문제로 3칸이상 연속으로 밟을수 없다는 제약은 같다.

그러나 2579-계단오르기 문제는 마지막계단을 반드시 밟아야 하기때문에

우리가 풀 문제인 포도주 시식은 마지막계단을 항상 밟을 필요가 없다.

(포도주 시식문제이지만 편의를위해 계단을 밟는다고표현)

그에따라 작성코드가 조금 바뀐다.

 

1번째,2번째, 3번째까지 똑같이 DP로 풀어주는데

3번째 최댓값부터 자기자신(마지막계단 일수도있는)을 밟을필요가 없을수 있다.

따라서 계산된 값과 자기자신의 바로 전 DP[i-1] 과 비교를 해줘서 큰값을 사용한다.

 

계단오르기 작성코드와 동시에 비교해본다면 무엇을 말하는것인지 이해하기 편하다.

 

작성 코드

#include <iostream>
#include <vector>
using namespace std;
int max(int a,int b)
{
	if(a<b) return b;
	return a;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	int n,temp;
	cin >> n;
	int v[10002];
	int dp[10002];
	for(int i=1;i<=n;i++)
	{
		cin>>v[i];
	}
	dp[1]=v[1];
	dp[2]=v[1]+v[2];
	for(int i=3;i<=n;i++)
	{
		int temp = max(dp[i-3]+v[i-1]+v[i],dp[i-2]+v[i]);
		dp[i] = (max(temp,dp[i-1]));
	}
	cout<<dp[n];
	return 0;
}

 

 

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

2156번: 포도주 시식