[C/C++] 백준 #2156 포도주 시식(탐욕 알고리즘)

이번 문제는 탐욕 알고리즘의 범주로 놓아야할 것 같아서, 탐욕 알고리즘이라고 적기는 했지만, 문제에서 추천하는 알고리즘은 동적 계획법입니다.  동적 계획법이 더 맞을 수도 있겠죠.

 

문제의 링크는 다음과 같습니다.

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

2156번: 포도주 시식

제가 생각한 알고리즘은 다음과 같습니다.

$f{c}_0$은 현재 와인을 선택하지 않았을 때, 최대값입니다.  $f{c}_1$은 이전 와인은 선택하지 않았지만, 현재 와인은 선택한 경우입니다.  $f{c}_2$은 이전와인과 현재 와인을 연이어서 선택한 경우입니다.  연달아 3잔의 와인을 선택하면 안 되기 때문에, 위의 3가지 경우만 따지면 됩니다.

 

wine glasses

$f{c}_0$는 현재 와인을 선택하지 않은 것이기 때문에 이전의 3개의 값 중 가장 큰 것을 선택합니다.

$$f{c}_0=max(f{c}_0,f{c}_1,f{c}_2)$$

$f{c}_1$은 현재 와인을 선택하지만 이전 와인은 선택하지 않는 것이기 때문에 이전의 $f{c}_0$에 현재 와인잔의 와인량을 더합니다.

$$f{c}_1=f{c}_0+w$$

$f{c}_2$는 현재 와인과 이전 와인을 연속으로 선택한 것이기때문에 이전의 $f{c}_1$에 현재 와인잔의 와인량을 더합니다.

$$f{c}_2=f{c}_1+w$$

이것을 반복하면 최종적으로 가장 많은 양의 와인을 마실 수 있는 경우의 양을 구할 수 있습니다.

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #2156
//        - by Aubrey Choi
//        - created at 2019-06-03
//------------------------------------------------
#include <stdio.h>
#include <memory.h>

int max(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, w, fc0 = 0, fc1 = 0, fc2 = 0;
    scanf("%d", &n);
    scanf("%d", &w);
    fc1 = w;
    for(int i = 1; i < n; i++)
    {
        scanf("%d", &w);
        int t = fc0;
        fc0 = max(fc0, fc1, fc2);
        fc2 = fc1 + w;
        fc1 = t + w;
    }
    printf("%d\n", max(fc0, fc1, fc2));
    return 0;
}