2156) 포도주 (C++)

 출처 

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

2156번: 포도주 시식

 내 풀이 

#include<iostream>

using namespace std;

int Glass[10001];
int DP[10001];
int N = 0;

int main()
{
	cin >> N;

	for (int i = 1; i <= N; i++)
	{
		cin >> Glass[i];
	}


	DP[1] = Glass[1];
	DP[2] = Glass[1] + Glass[2];
	int max_Glass = max(max(Glass[1], Glass[2]), Glass[3]);

	if (max_Glass == Glass[1]) DP[3] = Glass[1] + max(Glass[2], Glass[3]);
	else if (max_Glass == Glass[2]) DP[3] = Glass[2] + max(Glass[1], Glass[3]);
	else DP[3] = Glass[3] + max(Glass[1], Glass[2]);


	{
		for (int i = 4; i <= N; i++)
		{
			DP[i] = 
				max(
				max(
					DP[i - 1],
					DP[i - 2] + Glass[i]),
				DP[i - 3] + Glass[i - 1] + Glass[i]
			);
		}
	}
	
    //결과값 출력 
	cout << DP[N];

}

 

 해설

전에 풀었던 계단 오르기과 유형이 비슷했다.

https://xortl98.tistory.com/109

2579) 계단 오르기 (C++)

 

달라진 점은 무조건 첫번째 시작이 아닌 자유로운 시작이었고 무조건 마지막 변수를 걸칠 필요가 없다는 것이다.

그래서 N=3 인 경우, 경우의 수, 맨 마지막 출력만 바꿔서 풀어보았다.

 

N=3인 경우 5 8 7와 같이 2,3번 잔을 마시는 것이 최댓값인 경우가 있어서 조건문으로 3잔 중 최댓값을 찾은 후 

최댓값 잔에 나머지 2번째로 큰 잔의 값을 더해주는 식으로 풀었다.

 

경우의 수는 저번에 계단 오르기에서 풀었던 것에 공식 하나를 더 추가하였다. MAX->마실 수 있는 최댓값 

1. N+ MAX(N-2)

2. N + N-1 + MAX(N-3)

3. MAX(N-1)

 

3번의 경우는 계단 오르기와 다르게 마지막 잔을 꼭 마셔야 되는 것이 아니기 때문에 최댓값이 나올 수 있는 

마지막 값과 마지막 전값을 비교하였다. 

 

느낀점 

계단 2탄이었다. 조건문이 3개라 코드를 짜는데 고민이 많았는데 max를 2개 겹쳐 쓰면 된다는걸 알고 풀어보니 풀렸다.

b

사실 엄청 오래걸렸다.