C++) 백준 2156번 풀이_포도주 시식

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

2156번: 포도주 시식

술 문제가 나와서 정말 기뻤는데

후... 효주친구... 술 많이 먹여주고 싶었지만 네 번이나 실패했다.

아니 6잔이 놓여있으면~~ 다 먹으면 되지~~ 이걸 3잔연속 마실 수 없다는게 실화냐~~

 

무튼 틀렸을 때는 한 단계 더 생각해보자는 걸 알게된 문제...

 

 

 

2차원 배열을 만들어서,

이전 잔 바로 먹을 경우/ 1잔 뛰어넘고 먹을 경우

 

로 DP계산을 한 것 까진 좋았는데

분명 손으로 풀어봤을땐 다 맞았는데 계속 틀렸다는거다

 

 

그래서 찾아보니

무려

2잔을 뛰어넘고 마시는 경우의 수도 고려해야했다.

 

이전 스티커 문제와 마찬가지로

3잔 뛰어넘을경우 어짜피 중간에 한 잔을 마시는게 이득이기 때문에 그 경우는 고려하지 않는게 포인트.

 

 

그래서 뭐... 결국

이전 잔 바로 먹을 경우 / 3잔연속을 방지하기위해 몇 잔이든 뛰어넘고 먹을 경우

 

로 나눠서 DP계산을 하면 된다.

 

지금 집에 가고싶어서 조금 급하게 코드를 짜면 (더럽게) 됩니다.

 

	#include<stdio.h>
	#include<algorithm>
	using namespace std;
    
	int main(void) {
		int i, j, cnt, inp ;
		long long int alchohol[2][1001] = { 0 };

		scanf("%d", &cnt);
		scanf("%d", &inp);

		alchohol[0][1] = alchohol[1][1] = inp;

		scanf("%d", &inp);
		alchohol[0][2] = alchohol[1][1] + inp;
		alchohol[1][2] = inp ;
		for (i = 3; i <= cnt; ++i)
		{
			scanf("%d", &inp);
			alchohol[0][i] = alchohol[1][i - 1] + inp;
			alchohol[1][i] = max(max(alchohol[0][i - 2], alchohol[1][i - 2]), max(alchohol[0][i-3], alchohol[1][i-3])) + inp;
		}

		printf("%lld", max(max(alchohol[0][cnt], alchohol[1][cnt]), max(alchohol[0][cnt - 1], alchohol[1][cnt - 1])));

	
	}