[BOJ_2156_RN] 포도주 시식 Problem Solving

문제 출처 : https://www.acmicpc.net/problem/2156

문제 해결에 필요한 알고리즘 : DP ( Dynamic Programming )

해설

마시는 순서는 상관이 없기에 포도주를 1번부터 순서대로 마신다고 가정함. dp와 ar의 인덱스는 0번부터 시작함.

i = 0 일 때

dp[i][2] = dp[i][0] = 0

dp[i][1] = ar[i]

 

i > 0 일 때

dp[i][0] = max(dp[i - 1][0], dp[i - 1][1], dp[i - 1][2])

dp[i][1] = dp[i - 1][0] + ar[i]

dp[i][2] = dp[i - 1][1] + ar[i]

 

dp[선택한 포도주의 번호][연속으로 마신 포도주의 개수] = 마시는 포도주 양의 최댓값

ar[포도주의 번호] = 포도주의 양

 

이 점화식을 적용하면 max(dp[n - 1][0], dp[n - 1][1], dp[n - 1][2])가 마시는 포도주 양의 최댓값이 된다.

정당성 증명

마시는 순서는 상관이 없기에 포도주를 1번부터 순서대로 마신다고 가정함. dp와 ar의 인덱스는 0번부터 시작함.

 

i = 0 일 때

dp[i][2] = dp[i][0] = 0

dp[i][1] = ar[i]

 

i > 0 일 때

dp[i][0] = max(dp[i - 1][0], dp[i - 1][1], dp[i - 1][2])

dp[i][1] = dp[i - 1][0] + ar[i]

dp[i][2] = dp[i - 1][1] + ar[i]

 

dp[선택한 포도주의 번호][연속으로 마신 포도주의 개수] = 마시는 포도주 양의 최댓값

ar[포도주의 번호] = 포도주의 양

 

dp[i][0]는 현재 잔을 마시지 않은 선택이다. 이 때 최대 이익이 되는 경우는 이전 잔의 선택에서 제일 이득을 본 선택이다.

 

dp[i][1]는 포도주를 1번 연속으로 마셨을 때의 선택이다. 이 때 최대 이익이 되는 경우는 이전 잔을 마시지 않았을 때의 최댓값에 현재 포도주의 양을 더한 값이다. 이전 잔을 마시지 않았을 때의 최댓값은 (dp[i - 1][0])로 보장이 되어있다.

 

dp[i][2]는 포도주를 2번 연속으로 마셨을 때의 선택이다. 이 때 최대 이익이 되는 경우는 이전 잔을 1번 연속으로 마셨을 때 의 최댓값에 현재 포도주의 양을 더한 값이다. 이전 잔을 1번 연속으로 마셨을 때의 최댓값은 (dp[i - 1][1])로 보장이 되어있다.

 

첫잔의 경우는 이전에 마셨던 포도주의 결과가 없기에 따로 점화식을 세워주었다. 마시지 않았을 때는 아무것도 마시지 않았으므로 0이 되고 1번 연속으로 마셨을 때는 첫 잔의 양이 된다. 2번 연속으로는 마실 수 없으니 0이 된다.

 

마지막까지 전부 선택했을 때의 최댓값은 max(dp[n - 1][0], dp[n - 1][1], dp[n - 1][2])로 보장된다.

시간복잡도

이 코드에서는 dp테이블을 채우는데 N * 3만큼 순회한다. 따라서 시간복잡도는  가 된다.

포도주 시식 코드 [ C ]

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