2156

백준 2156번

Link: 2156번: 포도주 시식

---

문제 설명

문제를 보자마자 예전에 풀었던 계단 오르기와 비슷한 문제라는 생각이 들었다.

Link: 2579번: 계단 오르기

차이점이 있다면 계단 오르기의 경우 마지막 계단을 반드시 밟아야 했지만, 이 문제는 3잔을 연속으로 마실 수 없다는 제약을 제외하면 어떠한 제약사항이 없다는 점이다.

점화식으로 풀어야 한다는 점은 동일하다.

예전에 계단 오르기를 풀때 점화식 세우는 과정을 제대로 이해하지 못한 것 같다.

이번 문제에서도 점화식 세우는데 많은 어려움을 겪었고, 결국 에전에 풀었던 계단 오르기 문제를 다시 보면서 점화식을 어떻게 세워야 하는지 생각했다.

또, 마지막 계단을 반드시 밟아야 한다는 제약사항을 빼고 구현하는 방법에 대해서도 많이 고민했던것 같다.

결론적으로는 답을 찾아서 풀었다.

점화식 세우는 연습은 얼마나 해야 점화식을 세울 줄 알게 되려나??

---

정답 코드

//
// Created by Keith_Lee on 11/01/2019.
//

#include <iostream>
#include <vector>

using namespace std;

int N;

int maximum(vector<int> numbers){
    int result = 0;

    for(int i=0; i<numbers.size(); i++){
        if(numbers[i] > result){
            result = numbers[i];
        }
    }

    numbers.clear();
    return result;
}

int main(){
    cin >> N;

    int DP[10001];
    int score[10001];

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

    vector<int> to_compare;

    DP[1] = score[1];
    DP[2] = max(score[1] + score[2], score[2]);

    for(int i=3; i<=N; i++){
        to_compare.push_back(DP[i-1]);
        to_compare.push_back(DP[i-2] + score[i]);
        to_compare.push_back(DP[i-3] + score[i] + score[i-1]);
        DP[i] = maximum(to_compare);
    }

    cout << DP[N] << '\n';

    return 0;
}

---