[BOJ] DP 2156 포도주 시식 C++

2156번 포도주 시식

📝문제링크 : www.acmicpc.net/problem/2156

 

$dp[i]$ 에는 i 번째 포도주가 마지막일 때, 마실 수 있는 최대 포도주의 양이 저장된다.

3개의 포도주를 연속으로 선택할 수 없다는 제약조건이 있으므로, 아래 그림과 같이 3개의 경우의 수를 생각해 볼 수 있다. 

① x, y를 고르고 z는 선택하지 않는 경우

② x, z를 고르고 y는 선택하지 않는 경우

③ y, z를 고르고 x는 선택하지 않는 경우

 

이 세가지 경우의 수 중 max 값이 dp[i] 가 된다.

 

dp[i]의 값이 될 수 있는 3가지 경우의 수

앞에서 풀었던 문제(9465 스티커)는 arr[i] 값을 선택한다는 걸 가정하고 경우의 수를 찾았는데, 이 문제는 arr[i]를 선택하지 않는 경우까지 고려해야한다는 점을 간과하기 쉬워 배울점이 있는 문제였다.

 

소스코드

#include <iostream>
#include <algorithm>
using namespace std;

int    arr[10001];	//테이블의 포도주 정보가 저장됨
int    dp[10001];	//최대 포도주 양이 저장됨

int main()
{
    int	n;
	
    cin >> n;
	
    //get input
    for(int i = 1; i < n + 1; i++)
    {
        cin >> arr[i];
    }
	
    //set initial value
    dp[1] = arr[1];
    dp[2] = arr[1] + arr[2];

    //solve
    for(int i = 3; i < n + 1; i++)
    {
        dp[i] = max(dp[i - 3] + arr[i - 1] + arr[i], 
        			max(dp[i - 2] + arr[i], dp[i - 1]));
    }
    cout << dp[n] << '\n';
    return (0);
}

 

 

• max() 함수 중첩으로 쓰니까 편하다.