[2156번] 포도주 시식

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

다이나믹 프로그래밍을 공부하였다면 이 문제를 접할 때 바로 다이나믹 프로그래밍이라는 것을 느낄 수 있다.

하지만 다이나믹 프로그래밍도 식을 어떻게 구성하느냐에 따라 DP를 알아도 못푸는 경우가 허다하다.

이 문제는 연속으로 포도주 3개를 먹으면 안되고, 최대로 많이 마실 수 있는 방법을 찾는것이다.

DP[0]는 0이다.(0잔을 마셨으니)

DP[1]은 arr[1]을 따르고

DP[2]는 arr[1] + arr[2]를 따를 것이다. 

DP[3]부터가 시작인데, 3잔째에 최대가 될 수 있는 방법은, 

1번째 잔 마시고 3번째 잔 마시는 법, 2번째 잔 마시고 3번째 잔 마시는 법이 있다. 

3번째 잔만 마시는 것은 1번째 + 3번째보다 못하니 이런 방법은 존재하지 않는다.

즉, i번째 DP로 가면 결국

이전에 2잔 마셔와서 다음잔 스킵하고 그다음 잔 마시고 현재잔 마시는 법

즉, DP[i-3] + arr[i-1] + arr[i]이 있고,

이전잔까지 마셔온 것이 가장 큰 경우 DP[i-1],

현재 포도주의 2번째 전잔까지 마셔온것과 현재잔을 마시는 법

DP[i-2] + arr[i]가 있다.

이 3가지 중에서 최대값을 DP[i]에 저장하면 되니

DP[i] = max(DP[i - 3] + arr[i - 1] + arr[i], DP[i - 1], DP[i - 2] + arr[i]); 로 표현 할 수 있다.

소스 코드 : 

#include <stdio.h>
 
int max(int a, int b, int c) {
    if (b > c) {
        if (a > b) return a;
        else return b;
    }
    else {
        if (a > c) return a;
        else return c;
    }
}
int main()
{
    int n;
    int arr[10002];
    int DP[10002];
    int ans = 0;
 
    scanf("%d", &n);
 
    // 초기화
    for (int i = 0; i <= 10001; i++)
    {
        DP[i] = 0;
        arr[i] = 0;
    }
 
    for (int i = 1; i <= n; i++)
        scanf("%d", &arr[i]);
 
    
    DP[0] = 0;
    DP[1] = arr[1];
    DP[2] = arr[1] + arr[2];
 
    for (int i = 3; i <= n; i++)
    {
        DP[i] = max(DP[i - 3] + arr[i - 1] + arr[i], DP[i - 1], DP[i - 2] + arr[i]);
    }
    
    printf("%d", DP[n]);
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>