[BOJ, C++]#2156_포도주 시식, DP, 동적 프로그래밍, 동적 계획법

#1. 문제

https://www.acmicpc.net/problem/2156

 

---

 

#2. 풀이

 

1. DP

[알고리즘]#5_동적 계획법

DP는 주어진 문제의 입력 크기에 따라서 중복되는 하위 문제를 재귀적으로 해결하고, 이 결과 값들을 기억하는 것으로 중복 계산을 방지해 최적화를 수행하고, 결과적으로 최적 해를 찾아냅니다.

 

2. 3가지 경우 고려하여, dp [i]를 업데이트

//@조건1: i-2, i-1 번째 와인 마시고, i 번째 와인 안 마시기

= dp[i-1]

//@조건2: i-2, i 번째 와인 마시고, i-1 번째 와인 안 마시기

= dp[i-2] + wines[i]

//@조건3: i-1, i 번째 와인 마시고, i-2 번째 와인 안 마시기

= dp[i-2] + wines[i-1] + wines[i]

 

1. i번 째 와인 순서에서 최대로 마실 수 있는 와인 량을 계산하기 위해, 우리는 3가지 경우를 고려합니다.
2. 먼저, i번째 와인을 마시지 않고, i-2번과 i-1번 와인만 마시는 경우.
3. 그리고, i-1번째 와인을 마시지 않고, i-2번과 i번 와인만 마시는 경우
4. 마지막으로, i-2번째 와인을 마시지 않고, i-1번과 i번 와인만 마시는 경우
5. 결과적으로, i번 째 순서에서 최대로 마실 수 있는 와인의 양은 위 3가지 경우 중 최대가 되는 값이 되겠죠.

 

---

 

#3. 코드

/*
    @링크: https://www.acmicpc.net/problem/2156
*   @문제: DP 활용, i 번째 와인 순서에서 총 3가지 경우를 고려한 dp[i]를 계산하는 문제
*   @설명
        1. i 번째 와인에 대하여 3가지 경우를 고려하여, 그 중 최대 값을 dp[i]로 설정한다.
            조건1. i번째 와인을 안 마실 경우, i-2번과 i-1번 와인을 마실 경우: dp[i-1]
            조건2. i-1번째 와인을 안 마실 경우, i-2번과 i번 와인을 마실 경우: dp[i-2] + wines[i]
            조건3. i-2번째 와인을 안 마실 경우, i-1번과 i번 와인을 마실 경우: dp[i-3] + wines[i-1] + wines[i]
        2. dp[n]을 결과 값으로 출력
*/


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

#define MAX 10001

int n;
int wines[MAX], dp[MAX];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    //@포도주 양
    for(int i=1; i<=n; ++i)
    {
        cin >> wines[i];
    }

    //@1번째 와인 순서의 최대 값 - 무조건 마실 경우
    dp[1] = wines[1];
    //@2번째 와인 순서의 최대 값 - 1번 와인 먹고 2번 와인도 무조건 마실 경우
    if(n > 1)
    {
        dp[2] = wines[1] + wines[2];
    }

    //@3번 와인부터 DP 시작
    for(int i=3; i<=n; ++i)
    {
        //@조건1: i-2, i-1 번째 와인 마시고, i 번째 와인 안 마시기
        //@조건2: i-2, i 번째 와인 마시고, i-1 번째 와인 안 마시기
        //@조건3: i-1, i 번째 와인 마시고, i-2 번째 와인 안 마시기
        dp[i] = max({dp[i-1],
                    dp[i-2] + wines[i],
                    dp[i-3] + wines[i-1] + wines[i]});
    }

    cout << dp[n];

    return 0;
}

 

---