[백준 2156번/C언어] 포도주 시식, 동적계획법으로 풀이

백준 2156번 문제를 Dynamic Programming (DP, 동적 계획법)으로 풀어보았습니다. 

백준 2156번: https://www.acmicpc.net/problem/2156

2156번: 포도주 시식

 

문제 내용은 아래와 같습니다. 

 

목표했던 문제가 있어 동적계획법 공부를 시작하였는데, 목표했던 문제는 이미 해결했으나, 한 번 공부를 시작한 만큼 다른 문제들도 풀어보고 싶어서 이 문제를 골랐습니다. 동적계획법을 공부하고 싶으신 분들은 제 블로그에 관련된 문제를 푼 게시글이 있으니 참고해주시기 바랍니다. 동적계획법은 많이 접해보고, 나중에는 해당 문제가 동적계획법인지 모르고 접해도 점화식을 통해 풀어야겠다는 판단이 서는 것이 중요하다고 합니다. 따라서 저는 이번 기회에 동적계획법으로 풀 수 있는 예제를 최대한 많이 접해보려고 합니다. 

제가 푸는 문제들이 쉬운 수준이어서 그런지는 몰라도, 이제는 점화식을 세워야겠다는 것만 알면 비교적 쉽게 문제를 해결할 수 있게 되었습니다. 하지만 점화식을 세우는 것에 익숙하지 않거나 이를 인지하지 못할 경우 문제 난이도가 기하급수적으로 상승하게 됩니다. 따라서 동적계획법을 잘 모르신다면 기본적인 개념을 익히신 후 푸는 것을 추천드립니다. 아래 블로그에서 해당 내용을 잘 설명하고 있으니 참고해 주세요.

https://didu-story.tistory.com/220

[알고리즘] Dynamic Programming (동적 계획법, DP) (feat. Swift 스위프트)

 

 

코드를 구성하기에 앞서 점화식을 먼저 세워보았습니다. 점화식은 3개의 경우로 나누어서 세워보았고, 3가지 경우와 그에 따른 점화식은 아래와 같습니다. 최종 결괏값은 아래 세 가지 경우 중 가장 큰 값으로 결정됩니다. 

Case1: F(n) = F(n-1)
Case2: F(n) = amount [n] + amount[n-1] + F(n-3)
Case3: F(n) = amount[n] + F(n-2) 

위 경우들에 대해서 주어져있는 예제 입력을 통해 간략히 설명을 해보겠습니다.

n	amount[n]	F(n)
1	6	6
2	10	6 + 10 = 16
3	13	10 + 13 = 23
4	9	6 + 13 + 9 = 28
5	8	6 +10 + 9 + 8 = 33
6	1	6 +10 + 9 + 8 = 33

우선 첫 번째 케이스는 n이 6일 때 적용할 수 있습니다. 6은 1에 불과한데, 이미 amount[5]와 amount[4]를 연속적으로 선택한 상황이기 때문에, 만약 1을 선택할 경우 이 둘 중 하나를 포기해야 합니다. 이 경우에는 1을 포기하여 이전에 값을 지속하는 것이 최댓값을 유지하는 선택일 것입니다.

두 번째 케이스는 n이 5일 때 적용됩니다. 현재값인 8과 이전값인 9를 선택했기 때문에 n이 3일 때의 경우를 선택할 수 없고, 따라서 n이 2일 때까지의 최댓값을 더하여 최댓값을 산출하는 방식입니다.

마지막 케이스는 예제에서는 적용되는 경우가 없지만, 현재값을 선택하지만 n-1번째 값은 선택하지 않고, 따라서 n-2부터도 선택가능하기 때문에 n-2까지의 최댓값을 더하게 됩니다. 

즉, 각 경우들은 n번째 값을 선택할 것이냐 아니냐로 한 번, 그리고 n번째 값을 선택했으면 n-1번째 값을 선택할 것이냐 아니냐로 한 번 나누어, 세 번 연속으로 값을 선택하는 것을 막으면서 최댓값을 도출하는 것입니다. 

 

 

위에서 세운 점화식으로 코드를 구성하면 아래와 같습니다. 우선 res[2]까지는 반복문에 넣으면, 음수 인덱스가 발생할 수 있기 때문에, 값을 따로 넣어줍니다. res[0]은 n=1일 때로, 수가 하나밖에 없으므로, 입력받은 숫자를 그대로 넣어줍니다. n=2일 때는 주어진 값을 모두 더해도 3개가 연속으로 더해지기 않기에 주어진 두 개의 값을 모두 더한 값을 넣어줍니다. n=3의 경우 3개를 모두 선택하면 연속되기 때문에, 3개의 수를 2개씩 나눠 더한 값 중 가장 큰 값을 넣어줍니다. 

그리고 n=3부터 반복문에 넣어 위에 세운 세 가지 점화식을 적용하여 그중 가장 큰 값을 res 인덱스에 넣습니다. 반복문이 끝나면 n번째 결괏값(인덱스 n-1)을 출력하며 마무리합니다. 

#include <stdio.h>
#include <stdlib.h>

// 세 개의 정수를 비교하여 가장 큰 값을 return
int compare(int a, int b, int c) {
    int max = a;
    if (b > max) max = b;
    if (c > max) max = c;
    return max;
}

int main() {
    int n;
    scanf("%d", &n);
    
    int *score = (int *)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) scanf("%d", &score[i]);
    
    int *res = (int *)malloc(sizeof(int) * n);
    
    // 0~2까지 미리 설정
    res[0] = score[0];
    res[1] = score[0] + score[1];
    res[2] = compare(res[1], score[2]+score[1], score[2]+score[0]);
    
    // 반복문에서 점화식 적용하여 가장 큰 값을 res 배열에 저장
    for (int i = 3; i < n; i++) {
        res[i] = compare(score[i]+score[i-1]+res[i-3], score[i]+res[i-2], res[i-1]);
    }
    
    // n번째 결과를 출력
    printf("%d", res[n-1]);
    
    free(score);
    free(res);
}

 

 

마지막으로 아래 링크는 특수한 경우 및 일반적인 경우 별로 반례가 나와있는 블로그 글이니 문제를 풀 때 참고하시면 좋을 듯합니다. 

https://raejoonee.tistory.com/15

[백준/2156번/Java] 포도주 시식