[C++/BOJ] 백준 2156 포도주 시식 (DP)

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

2156번: 포도주 시식

 

백준 티어 : 실버 1

 

 

=> 포도주의 개수와 각각의 양이 주어질때, 3번연속으로 마시지 못한다는 제한이 있다.

이때 마실 수 있는 포도주의 양을 출력하는 문제이다.

 

해설 : 

DP를 이용하여 푸는 문제다.

3번연속으로 마실수 없다는 것을 염두해서 풀이해야한다.

 

크게 두가지의 경우가 있다.

1) n번 포도주를 마시지 않는 경우

2) n번 포도주를 마시는 경우 

 

n번째를 마시는 경우에는 또 2가지의 경우로 나뉜다.

 - 1] 1번째 연속으로 마시는 경우 (n-1번째는 마시지 않음)

 - 2] 2번째 연속으로 마시는 경우 (n-1번재는 마실거다.)

 

이렇게 총 3개의 경우를 생각해서 풀이하면 된다.

 

해설 코드 :

#include<iostream>

#include<algorithm>

#include<cstring>

using namespace std; //연속으로 3개를 못마심

//그때 최대로 마실수 있는 포도주의 양은?

int n;

int dp[10001]; // 최대값 저장

int arr[10001]; // 포도주의 각각의 양 저장

int main(){

     cin >> n;

     for(int i=1;i<=n;i++) cin >> arr[i];

     dp[1] = arr[1];

     dp[2] = arr[1]+arr[2];

 

     for(int i=3;i<=n;i++){

          dp[i] = dp[i-1]; // default == 안먹음

          if(dp[i] < dp[i-2]+arr[i]){ // i-1을 안먹었을 경우//연속 1번

          dp[i] = dp[i-2]+arr[i];

          }

          if(dp[i] < dp[i-3]+arr[i-1]+arr[i]){// i-1을 먹었을 경우//연속 2번

          dp[i] = dp[i-3]+arr[i-1]+arr[i];

          }

    }

     cout<<dp[n];

}

 

 

if(dp[i] < dp[i-2]+arr[i]){ // i-1을 안먹었을 경우//연속 1번

 

=> i-2번 까지의 최댓값과 현재 포도주의 양을 더한것을 넣어준다.

 

if(dp[i] < dp[i-3]+arr[i-1]+arr[i]){// i-1을 먹었을 경우//연속 2번

 

=> 연속 2번 이라는것은 i-1 과 i번을 먹었으믈 i-3은 먹지 못한다. 그러므로

i-3번 까지의 최댓값과 현재 포도주의 양 + i-1번째 포도주의 양을 더한것을 넣어준다.

 

 

문제 후기 :

처음에 재귀를 이용하여 풀어보려고 했는데 

나한테는 이 방식이 더 쉬운것같다.