백준 2156번 포도주 시식

문제링크 : https://www.acmicpc.net/problem/2156

2156번: 포도주 시식

오랜만에 백준 문제풀이잼

 

다이나믹 프로그래밍 적용하면 풀 수 있는 간단한 문제이다.

이 문제는 함수 하나만 제작하면 된다. 바로 그것은

 

i-1이 안먹은 상태일 때, 효주가 i번째 잔 부터 가장 많이 먹을 수 있는 포도주의 양

 

을 반환하는 함수를 생각해내면 문제가 아주 쉽다. 이 함수를 P(i), i번째 포도주의 양을 A(i) 라고 해보자.

 

연속으로 3잔을 모두 마실 수 없기때문에 바로 앞의 잔을 안먹은 상태라면 다음과 같은 상황이 있을 수 있다.

 

i번째 잔을 안 먹었을 때 ---> i번째 잔을 안먹은 상태이기 때문에, P(i+1)이 가장 많이 먹을 수 있는 포도주의 양

 

i번째 잔을 먹었을 때는 다시 두가지 경우로 나뉜다.

    i+1번째 잔을 안 먹었을 때 ---> A(i) + i+1번째 잔을 안먹은 상태이기 때문에, P(i+2)

    i+1번째 잔을 먹었을 때 ---> A(i) + A(i+1) + i+2번째 잔은 못먹기 때문에, P(i+3)

 

그러니까 결국 위의 3가지 상황중 가장 큰 값이 i번째 잔 부터 효주가 가장 많이 먹을 수 있는 포도주의 양 이다.

 

이제 이 상황을 프로그래밍 해주면 된다.

 

#include <stdio.h>
#include <algorithm> // max

using namespace std;

int a[10100], n;

int p(int i) {
    if (i==n) return a[n];
    else if (i==n-1) return a[n-1]+a[n];
    else if (i > n) return 0;
    else return max(max(p(i+1), a[i]+p(i+2)), a[i]+a[i+1]+p(i+3));
}

int main() {
    scanf("%d", &n);
    for (int i=1;i<=n;i++)
        scanf("%d", &a[i]);
    printf("%d\n", p(1));
    return 0;
}

P 함수의 구현은 간단하다. 우리가 나눠놓았던 경우의 수를 전부 계산해서 반환해주기만 하면 된다.

 

하지만 이 구현은 큰 문제가 있다. 바로 P(i)가 P(i+1), P(i+2), P(i+3)을 호출한다는 것이다. 이 말인 즉슨 P함수가 i단계마다 3배씩 증가하며 스택을 차지하게 되고 결국 stack overflow가 발생하게 될거라는 것이다.

 

위의 P함수는 손쉽게 캐싱해두어서 다이나믹 프로그래밍을 할 수 있다.

 

#include <stdio.h>
#include <algorithm> // max
#include <cstring> // memset

using namespace std;

int a[10100], n, c[10100];

int p(int i) {
    if (c[i] != -1) return c[i];
    if (i==n) return a[n];
    else if (i==n-1) return a[n-1]+a[n];
    else if (i > n) return 0;
    else return c[i] = max(max(p(i+1), a[i]+p(i+2)), a[i]+a[i+1]+p(i+3));
}

int main() {
    memset(c, -1, sizeof(int) * 10100);
    scanf("%d", &n);
    for (int i=1;i<=n;i++)
        scanf("%d", &a[i]);
    printf("%d\n", p(1));
    return 0;
}

별도의 C배열을 사용해서 각 P(i)의 값을 캐싱해 둠으로써 P함수가 C가 존재할때 다른 P함수들을 호출 하지 않도록 제작하였다.

 

뾰로롱