[C++] 백준 2156 - 포도주 시식

www.acmicpc.net/problem/2156

2156번: 포도주 시식

<풀이>

1. 포도주들을 입력받는다.

2. 최대 2잔까지 연속으로 마시면서, 마실 수 있는 포도주의 최대량을 계산하고 출력한다.

 

<해법>

1. DP 점화식

=> 점화식은 "현재 포도주를 마시거나, 마시지 않는 모든 경우 중 최댓값" 입니다. 모든 경우는 아래 그림과 같이 나타낼 수 있습니다.

 

#include <iostream>
#include <string.h>
#include <algorithm>
#define MAX 10000 + 1
 
using namespace std;
 
int n;
int wine[MAX];
int cache[MAX];
int answer;
 
int main() {
 
    //초기화
    n = 0;
    memset(wine, 0, sizeof(wine));
    memset(cache, 0, sizeof(cache));
    answer = 0;
 
    //입력
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> wine[i];
    }
 
    //해법
    cache[1] = wine[1];
    cache[2] = wine[1] + wine[2];
    for (int i = 3; i <= n; i++) {
        int case1 = cache[i - 3] + wine[i - 1] + wine[i]; //~XOO 와인 마신 경우
        int case2 = cache[i - 2] + wine[i]; //~XO 와인 마신 경우
        int case3 = cache[i - 1]; //~X 와인 마신 경우
 
        cache[i] = max(max(case1, case2), case3);
    }
 
    //결과 갱신
    answer = cache[n];
 
    //출력
    cout << answer << "\n";
 
    //종료
    return 0;
}

 

DP에 대해 알아볼 수 있는 문제였습니다.