(2156)(DP) 백준 포도주 시식

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

풀이

---

N잔의 포도주가 일렬로 놓여있다. 포도주 시식을 하는데 2가지 규칙이 존재한다.

1. 포도주 잔을 선택하면 모두 마셔야하고, 마신후에는 제자리에 다시 놓아야 한다.

2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.  ex) x o x o o o x 와 같은 경우는 불가하다.

위의 조건을 만족하면서 용량이 큰 포도주만 잘 골라마셔서 누적 최대 합을 만드는 알고리즘을 짜야한다. 

동적 계획법 알고리즘을 짤때 가장 핵심은 주어진 문제를 부분 문제로 나누어 생각해야하고 나눈 부분으로 전체 문제에서 나타날 수 있는 전체 경우의 수를 표현 할 수 있어야한다.

노트를 펴서 규칙을 나누고 생각해보면 3가지 부분으로 전체 문제를 쪼갤 수 있다. 

1. n번째 배열 arr[n]에서 arr[n-1]을 선택하여 마실경우

---

arr[n-5]    arr[n-4]    arr[n-3]    arr[n-2]    arr[n-1]    arr[n] 이라고 치면 arr[n-2]는 무조건 X(안마심)여야 한다.

arr[n-2]가 X라고 하면 arr[n-3]은 O or X 즉, 마실수도 안 마실 수 도 있지만 최대합을 구하는 문제에서 X(안마심)을 고를 필요는 없기 때문에 

arr[n-3]을 마시게 되고 최종적으로

arr[n-5]    arr[n-4]    arr[n-3]    arr[n-2]    arr[n-1]    arr[n] 

O or X    /  O or X    /     O     /       X       /       O     /      O    /

dp[n] = dp[n-3] + arr[n-1] + arr[n]; 라는 식이 나오게 된다.

2. n번째 배열 arr[n]에서 arr[n-1]을 선택하지 않은 경우 

---

1번 경우와 마찬가지로 arr[n-1]을 선택하지 않으면 arr[n-2]는 무조건 마시는게 좋기 때문에

arr[n-5]    arr[n-4]    arr[n-3]    arr[n-2]    arr[n-1]    arr[n] 

O  or  X  /  O or X  /  O or X   /       O      /     X        /     O    /

dp[n] = dp[n-2] + arr[n]; 과 같은 식이 나오게 된다.

3. n번째 배열을 arr[n]을 선택하지 않을 경우

---

arr[n]을 마시지 않으면 arr[n-1]은 선택하지 않아서 마시지 않을 이유가 없다.  그래서

arr[n-5]    arr[n-4]    arr[n-3]    arr[n-2]    arr[n-1]    arr[n] 

 O or X  /   O  or  X /  O or X   /  O or X   /     O     /       X    /

dp[n] = dp[n-1]; 과 같은 식이 나오게 된다.

위의 세 경우를 종합하여 프로그래밍 하면 정답을 출력 할 수 있다.

#include <stdio.h>
 
#define max(a, b) a>b ? a:b
 
 
 
int main() {
    int N;
    int arr[10001] = { 0 };
    int dp[10001] = { 0 };
    scanf("%d", &N);
    for (int i = 1; i <= N; i++) {
        scanf("%d", &arr[i]);
    }
    
    dp[1] = arr[1];
    dp[2] = arr[1] + arr[2];
    for (int i = 3; i <= N; i++) {
        dp[i] = max(dp[i-3] + arr[i-1] + arr[i], dp[i-2] + arr[i]);
        dp[i] = max(dp[i], dp[i - 1]);
    
    }
    
    printf("%d", dp[N]);
 
    return 0;
 
}