[BOJ] - 2156. 포도주 시식

[URL]

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

2156번: 포도주 시식

 

[풀이 과정]

*다이나믹 프로그래밍(dp)

 

arr[ ] : 인덱스 별로 와인의 양을 입력받아 저장

dp[ ] : 인덱스까지 가능한 최대치 양을 더한 값을 저장 (메모이제이션, 캐싱)

 

dp[0], dp[1]까지는 무조건 arr[0], arr[0] + arr[1] 해주는 것이 최대치

 

arr[2] 부터는 제한 사항을 따라야 한다. 즉, 연달아 3개의 와인을 선택하는 것이 안됨

 

이외에 index = n 인경우, 가능한 방법 3가지로 나눈다.

 

1) arr[n] + arr[n- 1] (n, n-1 두가지 선택O)  +  dp[n-3] (n-2 선택X -> 따라서 n-3까지의 최대치를 합산)

2) dp[n - 1] (현재 위치 n 선택X)

3) arr[n] (현재 위치 n 선택O) + dp[n - 2]  (n-1 선택X )

 

* 점화식이 가장 중요하다.

2부터 dp[n] =  dp[i] = MAX(dp[i - 3] + arr[i - 1] + arr[i], dp[i - 1], dp[i - 2] + arr[i]);

 

 

[소스 코드]

#include <stdio.h>
#include <cstring>
 
int arr[10005];
int dp[10005];
 
int MAX(int a, int b, int c) {
    if (a >= b)
    {
        if (a >= c)
            return a;
        else
            return c;
    }
    else
    {
        if (b >= c)
            return b;
        else
            return c;
    }
}
 
int main() {
 
    memset(dp, 0, sizeof(int) * 10005);
 
    int N;
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++)
    {
        scanf("%d", arr + i);
    }
 
    dp[0] = arr[0];
    dp[1] = arr[0] + arr[1];
 
    for (int i = 2; i < N; i++)
    {
        dp[i] = MAX(dp[i - 3] + arr[i - 1] + arr[i], dp[i - 1], dp[i - 2] + arr[i]);
    }
    printf("%d\n", dp[N - 1]);
 
    return 0;
}