[백준/c++] 2156번: 포도주 시식

 

 

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

2156번: 포도주 시식

 

N잔의 포도주가 있다. 연속 3잔은 마실 수 없고, 가장 많은 포도주를 마실 수 있도록 해야 한다. 마신 총포도주의 최댓값 출력하라.

이 문제는 BOJ 2579: 계단 오르기 문제와 유사하다! 그러나 여기서는 두 잔을 연속으로 안 마실 수 있다는 점이 다른데, 이 부분이 헷갈렸다.ㅠ0ㅠ

 

1. dp 이차원 배열을 정하기

 

dp[i][0] = i-1번째 잔을 마시는 경우

dp [i][1] = i-1번째 잔을 마시지 않는 경우

 

2. 초기값 정하기

 

dp [1][0] = wine [1]; dp [1][1] = wine [1];

만약 포도주의 개수가 2보다 작으면 dp [2]에 대해서 할 필요가 없으므로 dp [2]의 경우는 2보다 크거나 같은 때 진행해준다.

 

3. 점화식 구하기

 

우선 i개의 잔이 있다고 가정하고 진행해보자. i번째 잔을 먹기 전까지 어떤 잔들을 마셨고, 얼마큼의 잔을 마셨는지 dp에 저장하도록 구현한다.

//i-1잔을 마시는 경우
//dp[i-1][0]를 더하면 연속 3잔을 마시게 되므로 패스
dp[i][0] = wine[i] + dp[i-1][1]; 

//i-1잔을 마시지 않는 경우
dp[i][1] = wine[i] + max(dp[i-2][0], dp[i-2][1]);

 

여기서 주의할 것은!! 바로 두 잔을 연속으로 마시지 않는 경우가 있다는 것이다.

위의 코드는 0잔, 1잔을 연속으로 마시는 않는 경우이므로 2잔을 연속으로 마시지 않는 경우도 추가해줘야 한다!

//앞에서 해줬던 i-1번째 잔을 먹지 않는 경우와 비교

dp[i][1] = max(dp[i][1], max(dp[i-3][0], dp[i-3][1]) + wine[i]);

 

 

4. 출력하기

 

1부터 차례대로 N까지 i개의 포도주를 마시면서 최댓값을 저장해왔다.

더 큰 값을 출력해주자.

#include <iostream>
#include <algorithm>
#define num 10002
using namespace std;
int n, wine[num], dp[num][2];

void input(){
    cin >> n;
    for(int i=1; i<=n; i++) cin >> wine[i];
}

void solution(){
    dp[1][0] = wine[1]; dp[1][1] = wine[1];
    
    if(n>=2){
        dp[2][0] = wine[1] + wine[2];
        dp[2][1] = wine[2];
    }

    for(int i=3; i<=n; i++){
        dp[i][1] = wine[i] + max(dp[i-2][0], dp[i-2][1]); //두 잔 넘긴 상태
        dp[i][1] = max(dp[i][1], max(dp[i-3][0], dp[i-3][1]) + wine[i]); //두 잔을 연속으로 안먹은 상태
        dp[i][0] = wine[i] + dp[i-1][1];
    }
    
    cout << max({dp[n][0], dp[n][1], dp[n-1][0], dp[n-1][1]}) << '\n';
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    solution();
    return 0;
}

 

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!