[백준] 2156번 포도주 시식 c++

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

2156번: 포도주 시식

문제

효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오. 

예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.

입력

첫째 줄에 포도주 잔의 개수 n이 주어진다. (1≤n≤10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다.

출력

첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력한다.

 

 

문제접근 및 풀이

점화식을 통해 해결한다.

i번째 포도주까지 고려한 경우를 생각해보면

3잔연속으로 마실 수 없으므로 다음 시나리오가 존재한다.

1. i-3번째를 마시고 i-1,i번째를 마신다.

2. i-2번째를 마시고 i번째를 마신다.

3. i-1번째를 마시고 i번째를 마시지 않는다. -> 이게 중요했다. i번째를 마시지않고 i-1를 마시는 경우가 더 큰값을 가질수 있다. -> 여러 잔을 건너뛸수 있기 때문이다.

#include <iostream>
#include <algorithm>

using namespace std;

int main(){
    int n; cin >> n;
    int a[10001]={0};
    int dp[10001]={0};
    for(int i=1; i<=n; i++) scanf("%d", &a[i]);
    dp[0] = 0;
    dp[1] = a[1];
    dp[2] = a[1] + a[2];
    for(int i=3; i<=n; i++){
        dp[i] = max({dp[i-3]+a[i-1]+a[i], dp[i-2]+a[i], dp[i-1]});
    }
    printf("%d\n", dp[n]);
}

 

느낀점

점화식의 위력을 알게 되었다. 항상 재귀로 가지치기하는 식으로 dp문제를 해결했었다. 이 문제도 최적을 해를 점화식을 통해 찾기 보다 처음에, 해당 포도주를 먹는 경우 먹지 않는 경우를 재귀형식으로 하여 모든 가능한 경우중 최대값을 찾으려 하니 자연스레 시간초과가 났다. 하지만 점화식을 찾고 O(n)만에 답을 구할 수 있다는 것에 놀랐다. 더 dp 공부를 해야 겠다.