[Dynamic Programming] 백준 2156번 "포도주 시식" C++ 풀이

문제 링크

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

풀이

• 포도주는 두 잔까지만 연달아 마실 수 있다.
• Wine 라는 배열이 존재하며, Wine[N] 은 N 번째 잔의 양을 의미한다.
• D 라는 배열이 존재하며, D[N] 은 N 번째 잔까지 탐색했을 때의 마실 수 있는 최대 양을 의미한다.
  • D[4] 는 4번째 잔까지 탐색했을 때, 마실 수 있는 최대 양을 의미한다.
• D[N] 은 아래와 같은 경우의 수로 계산할 수 있다.
  • Wine[N] 번째 잔을 마신다.
    • Wine[N - 1] 번째 잔을 마셨을 경우
      • Wine[N - 1] 번째 잔과 Wine[N] 번 째 잔까지 총 2 잔을 마셨으므로, 더 이상의 잔을 더할 순 없다.
      • 따라서, D[N] 은, [N - 3] 번째 잔까지 마신 포도주의 양 D[N - 3] 에, [N - 1] 번째 잔의 양 Wine[N-1] 과 N 번째 잔의 양 Wine[N] 을 더해서 계산한다.
        • D[N] = D[N - 3] + wine[N - 1] + wine[N]
    • Wine[N - 1] 번째 잔을 마시지 않았을 경우
      • [N - 2] 번째 잔까지 마신 포도주의 양 D[N - 2] 에, N 번째 잔의 양 Wine[N] 을 더해서 계산한다.
        • D[N] = D[N - 2] + wine[N]
    • 마지막으로, 둘 중에 어느 경우가 더 마신 경우인지 모르기 때문에, 더 큰 값을 가려낸다.
      • D[N] = max(D[N - 3] + wine[N - 1] + wine[N], D[N - 2] + wine[N])
  • Wine[N] 번째 잔을 마시지 않는다.
    • Wine[N - 1] 번째 잔까지 탐색했을 때의 마실 수 있는 최대 양을 그대로 사용한다.
      • D[N - 1]
• 따라서, 마지막에 D[N] 과 D[N - 1] 을 다시 한번 더 비교하여, 더 큰 값을 실제 D[N] 에 삽입한다.
  • D[N] = max(D[N], D[N - 1])

테스트케이스

• [ 6, 10, 13, 9, 8, 1]
  • 6, 10, 13, 8 → 33
• [ 10, 13, 1, 2, 5, 11 ]
  • 10, 13, 5, 11 → 39
• [0, 1, 2, 200, 200, 1]
  • 1, 200, 200 → 401

코드

#include <iostream>
#include <vector>

using namespace std;

// 포도주 목록
vector<int> Wine;

// 최대 포도주 양 목록
vector<int> D;

// 최대값 반환 함수
int max(int a, int b){
    return a > b ? a : b;
}

int dynamic(){

    // 최대 포도주 양 목록의 idx 는 4부터 시작
    for(int i=3; i<Wine.size(); ++i){

        // W_i 를 마셨을 경우와 W_i 를 마시지 않았을 경우를 비교해, 최대 포도주 양 추가
        D.push_back(max(max( D[i-3] + Wine[i-1] + Wine[i], D[i-2] + Wine[i]), D[i-1]));
    }

    // 최대 포도주 양 목록의 마지막 요소 반환
    return D[Wine.size()-1];

}

int main(){

    // 포도주 개수 입력
    int n;
    cin >> n;

    // 포도주 목록과 최대 포도주 양 목록의 초기 3개는 0 으로 초기화
    for (int i=0; i<3; ++i){
        Wine.push_back(0);
        D.push_back(0);
    }

    // 포도주 목록 입력
    int k;
    for (int i=0; i<n; ++i){
        cin >> k;
        Wine.push_back(k);
    }

    cout << dynamic() << endl;

}

참고

• https://miiinnn23.tistory.com/10
• https://yabmoons.tistory.com/18