[백준]2156-포도주 시식(Dynamic Programming)

이 문제는 2579번 계단 오르기 문제와 매우 흡사하다.

다만 하나의 조건이 빠졌다. 다만 그 조건이 계산의 편의를 돕는 조건이었기 때문에 조건이 빠졌다고 계산이 쉬워진 게 아니라, 중간에 하나의 계산이 추가됐다.

https://everyyy.tistory.com/71

[백준]2579-계단 오르기(Dynamic Programming)

일단은 위 포스팅을 참고하면 좋다.

계단 오르기에서는 있었지만 이 문제에서 없어진 조건은 "무조건 1칸이나 2칸을 전진해야 한다."라는 조건이다.

따라서 1, 2번째 포도주를 선택하고 3, 4번째 포도주를 선택하지 않고 5, 6번째 포도주를 선택해도 된다는 것이다.

 

여기서 조금 생각해보면, 3개 연속으로 건너뛰는 경우는 없다. 왜냐하면 포도주의 양은 "음이 아닌 정수"이기 때문이다.

즉 고작 1이라고 해도 공으로 얻을 수 있는 수를 버릴 필요가 없다는 것이다.

모든 선택을 했는데 연속된 3개의 포도주가 선택되지 않았다고 치자. 그러면 그 3개의 포도주 중에서 가운데 포도주를 선택해도 어떠한 문제가 생기지 않는다. 그렇기 때문에 연속된 3개를 선택하지 않는 경우는 없다.

 

그러면 첫 번째 포도주부터 선택하면서 나아간다고 치면, n번째 포도주에서는 3가지의 경우가 있다.

• n - 1번째 포도주를 선택한 후 n번째 포도주를 선택하는 경우. 이 경우에는 n - 1번째 포도주는 무조건 n - 3이나 n - 4번째 포도주를 선택한 후 선택된 포도주이다. 왜냐하면 n - 2번째 포도주를 선택한 경우 n - 2, n - 1, n으로 3개 연속된 포도주를 선택하는 경우가 되기 때문이다.
• n - 2번째 포도주를 선택한 후 n번째 포도주를 선택하는 경우. 이 경우에는 제약이 없다. n - 1번째 포도주는 선택하지 않는다는 전제이기 때문에 제약조건에 걸리지 않는다.
• n - 3번째 포도주를 선택한 후 n번째 포도주를 선택하는 경우. 이 경우에도 마찬가지로 제약이 없다.

이를 코드로 표현하면 다음과 같다.

//#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
 
int grape(int N);
int max(int* ary);
 
int main() {
    int N;
    scanf("%d", &N);
    printf("%d\n", grape(N));
}
 
int grape(int N) {
    if (N < 2) {
        int quantity;
        scanf("%d", &quantity);
        return quantity;
    }
 
    int** ary = new int* [N + 1];
    ary[0] = new int[3]{ 0, };
    for (int i = 1; i <= N; i++) {
        ary[i] = new int[3]{ 0, };
        int quantity;
        scanf("%d", &quantity);
        ary[i][0] = ary[i][1] = ary[i][2] = quantity;
    }
    ary[2][0] += ary[1][0];
 
    for (int i = 3; i <= N; i++) {
        ary[i][0] += ary[i - 1][1] > ary[i - 1][2] ? ary[i - 1][1] : ary[i - 1][2];
        ary[i][1] += max(ary[i - 2]);
        ary[i][2] += max(ary[i - 3]);
    }
    int value = max(ary[N - 1]) > max(ary[N]) ? max(ary[N - 1]) : max(ary[N]);
    for (int i = 0; i <= N; i++)
        delete[] ary[i];
    delete[] ary;
 
    return value;
}
 
int max(int* ary) {
    int max = ary[0];
    if (max < ary[1])
        max = ary[1];
    if (max < ary[2])
        max = ary[2];
    return max;
}

링크로 올린 계단 오르기 문제와 함께 보면 이해가 더 잘 될 것이다.