백준 2156 포도주 시식

이 문제는 조금 의미가 있었다고 할까.. 

일단 문제를 처음 보고 든 생각은

뭔 개소리지..

였는데, 잘 보니까 계단 오르기 문제랑 비슷한거 같더라

근데, 설마 완전 같은 문제일까.. 하고 곰곰히 생각해보니

이건 계단 오르기 문제랑 다르게 '더블점프뿐만 아니라 트리플 점프도 허용하고, 마지막 계단을 밟지 않아도 돼는' 계단 오르기 문제 이더라

쿼드라점프.. 그러니까 한번에 4계단 오르는 점프도 가능하지만, 그렇게 뛸 바에는 중간에 밟는게 당연히 이득이다. 음수가 없으니까! 

트리플 점프를 하는 경우는

예를 들어

99 99 1 1 99 99 

이런 경우

구구(구구단 아님 ㅎ) 먹구 구구 먹구 트리플 뛰어서 구구 먹구 구구 먹구 하는게 젤 많이 마시는거니까, 이런 상황에서만 트리플점프를 쓴다.

그리고 마지막 계단을 안밟는게 이득인 경우는 예제의 경우와 같이

6 10 13 9 8 1

이런 상황인데

solve(n-1) 과 solve(n-2)를 비교하면, 전자는 32가 나오고 후자는 33이 나온다

왜냐면 1을 안밟게 되면 9와 8을 밟을 수 있으니까!

그래서 코드를 첨에 이렇게 짰다

 #include <iostream>
#include <algorithm>
using namespace std;

int memo[10001];
int wine[10001];

int max3(int a, int b, int c) {
	return max(max(a, b), c);
}
int solve(int n) {
	if (memo[n] > 0) {
		return memo[n];
	}
	int case1 = solve(n - 2) + wine[n]; //O X O
	int case2 = solve(n - 3) + wine[n - 1] + wine[n]; //O O X O 
	int case4 = solve(n - 4) + wine[n - 1] + wine[n]; //O O X X O -> triple jump

	return memo[n] = max3(case1, case2, case4);
}
int main() {
	int wineN;
	cin >> wineN;
	for (int i = 0; i < wineN; i++) {
		cin >> wine[i];
	}
	memo[0] = wine[0]; 
	memo[1] = wine[1] + wine[0];
	memo[2] = max(wine[1] + wine[2], wine[0] + wine[2]);
	memo[3] = max(wine[0] + wine[1] + wine[3], wine[0] + wine[2] + wine[3]);

	cout << max(solve(wineN - 2), solve(wineN - 1)) << endl;
}

DP(n) = max(

DP(n-2) + wine[n],

DP(n-3) + wine[n-1] + wine[n],

DP(n-4) + wine[n-1] + wine[n]

)

DP(n)은 'n개의 와인잔이 있을때 가장 많이 마실 수 있는 양' 이고

wine[n]은 'n번째 와인잔의 와인의 양' 이다.

근데 이렇게 제출 했더니

런타임에러가 떴다!!!

컴파일 에러도 아니고 오답도 아니고 에러라...

0으로 나눠지는 경우도 없으니 배열 인덱스의 오류일까 싶어서 잘 살펴봤더니

n이 1일경우가 문제더라

solve()함수의 파라미터가 -1로 들어가는 경우가 있는데

배열의 인덱스로 음수를 접근하니 당연히 에러..

그래서 이렇게 고쳤더니 정답.

(비쥬얼 스튜디오는 에러를 안내는데, 역시.. 코드블록을... 써야...)

#include <iostream>
#include <algorithm>
using namespace std;

int memo[10001];
int wine[10001];

int max3(int a, int b, int c) {
	return max(max(a, b), c);
}
int solve(int n) {
	if (n < 0) {
		return 0;
	}
	if (memo[n] > 0) {
		return memo[n];
	}
	int case1 = solve(n - 2) + wine[n]; //O X O
	int case2 = solve(n - 3) + wine[n - 1] + wine[n]; //O O X O 
	int case3 = solve(n - 4) + wine[n - 1] + wine[n]; //O O X X O -> triple jump

	return memo[n] = max3(case1, case2, case3);
}
int main() {
	int wineN;
	cin >> wineN;
	for (int i = 0; i < wineN; i++) {
		cin >> wine[i];
	}
	memo[0] = wine[0]; 
	memo[1] = wine[1] + wine[0];
	memo[2] = max(wine[1] + wine[2], wine[0] + wine[2]);
	memo[3] = max(wine[0] + wine[1] + wine[3], wine[0] + wine[2] + wine[3]);

	cout << max(solve(wineN - 1), solve(wineN - 2)) << endl;
}