백준 2156번 포도주 시식

문제 링크입니다:https://www.acmicpc.net/problem/2156

백준 2579번 계단오르기 문제(http://jaimemin.tistory.com/355?category=988050)와 상당히 비슷한 문제였습니다.

#include <iostream>

#include <algorithm>

using namespace std;

 

int wine[10001];

int cache[10001] = { 0 };

int wineCnt; //포도주 갯수

 

int maxSum(void)

{

        cache[1] = wine[1];

        cache[2] = wine[1] + wine[2];

 

        if (wineCnt == 1)

               return cache[1];

        else if (wineCnt == 2)

               return cache[2];

        else

        {

               for (int i = 3; i <= wineCnt; i++)

                       //계단 문제와 유사하나 한가지 추가한 점은 현재의 포도주를 안 마셨을 경우

                       //*계단 오르기 문제는 끝이 고정이였기 때문에 cache[i-1]을 고려할 필요가 없었다

                       //부연 설명: 차례대로 현재 포도주를 마시지 않을 경우, 현재 포도주를 마시되 이전 포도주를 마시지 않을 경우

                       //현재와 이전 포도주를 마셨기 때문에 i-2번째 포도주 시음할 수 없음 따라서 cache[i-3]을 더해줌

                       cache[i] = max(cache[i - 1], max(cache[i - 2] + wine[i], cache[i - 3] + wine[i - 1] + wine[i]));

               return cache[wineCnt];

        }

}

 

int main(void)

{

        cin >> wineCnt;

 

        for (int i = 1; i <= wineCnt; i++)

               cin >> wine[i];

        cout << maxSum() << endl;

        return 0;

}

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~