효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.
효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오.
예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.
첫째 줄에 포도주 잔의 개수 n이 주어진다. (1≤n≤10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다.
첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력한다.
#include <iostream>
#include <cstring> // memset
using namespace std;
/* 조건 */
#define MAX_N 10001
/* 변수 */
int N;
int wine[MAX_N], memo[MAX_N];
/* 함수 */
int max3(int a, int b, int c) {
return max(a, max(b, c));
}
int dp(int idx) {
if(idx < 0) return 0;
int& ret = memo[idx];
if(ret > -1) return ret;
return ret = max3(dp(idx-1), wine[idx] + dp(idx-2), wine[idx] + wine[idx-1] + dp(idx-3));
}
int main() {
/* 입력 */
cin >> N;
for(int i = 0; i < N; i++) {
cin >> wine[i];
}
/* 풀이 */
memset(memo, -1, sizeof(memo));
/* 출력 */
cout << dp(N-1) << '\n';
}
이 문제는 [02578] 계단오르기 문제와 비슷하다.
단, 이 문제는 건너 뛸 수 있는 횟수의 제한이 없다는 점을 고려해 최댓값을 구해야 한다.
N번째 와인잔에 대하여 취할 수 있는 행위(?)는 다음 세가지가 된다.
1. N을 건너뛴다.
2. N을 마시고 N+1을 건너뛴다.
3. N과 N+1을 마시고 N+2를 건너뛴다.
위의 세가지 경우가 어떤 것이든 무한히 반복돼도 조건에 부합하는 모든 경우가 된다.
따라서 위를 반복해 N에 return되는 값이 정답이 된다.
백준 [02156] 포도주 시식
https://www.acmicpc.net/problem/2156