[백준 2156번] 포도주 시식 (C++)

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

2156번: 포도주 시식

---

포도주 시식 문제는 N이 최대 10,000이므로 모든 경우의 수를 계산하는 경우 시간 초과가 발생할 수 있습니다.

포도주 시식 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다.

 

테이블 d[i]는 i번째 포도주까지 시식했을 때의 최대 포도주의 양으로 정의했습니다.

초기 값 d[1] = 첫번째 포도주의 양, d[2] = 첫번째 포도주의 양 + 두번째 포도주의 양입니다. 

연속으로 놓여있는 3잔을 모두 마실 수 없다는 제한을 고려했을 때, d[i]의 값은 세가지가 될 수 있습니다. 이 중 가장 큰 값을 취하면 됩니다.

• i - 1번째 포도주까지 시식 했을 때의 최대 포도주 양
• i - 2번째 포도주까지 시식 했을 때의 최대 포도주 양 + i번째 포도주 양
• i - 3번째 포도주까지 시식 했을 때의 최대 포도주 양 + i - 1번째 포도주 양 + i번째 포도주의 양

아래는 Bottom-Up 방식의 다이나믹 프로그래밍 코드입니다.

#include <bits/stdc++.h>
using namespace std;

int arr[10010], d[10010];   // d[i]는 i번째 포도주까지 시식했을 때의 최대 포도주 양

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n; cin >> n;
    for(int i = 1; i <= n; i++) cin >> arr[i];
    
    d[1] = arr[1]; d[2] = arr[1] + arr[2]; // 초기값
    for(int i = 3; i <= n; i++)
        d[i] = max({d[i - 3] + arr[i - 1]+ arr[i], d[i - 2] + arr[i], d[i - 1]});

    cout << d[n];
}

아래는 문제 풀이에 사용된 테스트케이스입니다.

6
6 10 13 9 8 10000
-> 10031

6
15 10 13 9 8 10000
-> 10037

3
15 10 13
-> 28