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

문제

백준 2156

2156번: 포도주 시식

풀이

dp 배열은 (인덱스, 몇번 연속으로 마셨는지) 중에서 최댓값을 나타냅니다.

예제로 보겠습니다.

	6	10	13	9	8	1
0	0	6	16	23	28	33
1	6	10	19	25	31	29
2	0	16	23	28	33	32

먼저 1번째, 6일 때 안 마시는 경우(dp[0][0])를 0, 2번 연속 마시는 경우는 없으니 0으로 초기화 해줍니다.

1번 연속 마시는 경우에는 arr[0]값인 6을 넣어줍니다.

 

2번째에서 안 마시는 경우는 dp[i-1][0~2] 중에서 최댓값을 넣어줍니다.

마시는 경우에는 2가지 경우가 있습니다.

 

1. 6을 마신 경우

2번 연속 마시게 됩니다. dp[1][2]에 10+6인 16을 넣어줍니다.

 

2. 6을 마시지 않은 경우

1번 연속 마시게 됩니다. dp[1][1]에 10을 넣어줍니다.

 

이렇게 i 번째에서는 dp에 다음과 같이 넣어줍니다.

1. 마시지 않을 때 : dp[i-1][0~2] 중에서 최댓값을 dp[i][0]에 넣습니다.

2. 1번 연속 마실 때 : dp[i-1][0] (그 전에 마시지 않아야 하므로) + arr[i]값을 dp[i-1][1]에 넣어줍니다.

3. 2번 연속 마실 때 : dp[i-1][1] (그 전에 한 번 마셔야 하므로) + arr[i]값을 dp[i-1][2]에 넣어줍니다.

문제 조건에서 3번 이상 연속으로 마시는 경우는 없습니다.

따라서 n-1까지 반복해준뒤, dp[n-1][0~2] 중에서 최댓값을 출력해주면 됩니다.

 

다른 예시입니다.

	100	100	1	1	100	100
0	0	100	200	200	201	301
1	100	100	101	201	300	301
2	0	200	101	102	301	400

백준 2579

2579번: 계단 오르기

비슷한 문제인 2579와 다른 점은, 와인은 계속해서 안 마실 수도 있다는 것입니다.

위에서 1, 2번째 와인을 마시고 5, 6번째 와인을 마시는 경우일 때 최댓값 400을 가집니다.

소스 코드

#include<iostream>
#include<algorithm>
using namespace std;
 
int n;
int arr[10000];
// dp[인덱스][몇번 연속으로 마셨는지]
int dp[10000][3];
int maxsum;
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    dp[0][1] = arr[0];
    for (int i = 1; i < n; i++)
    {
        // 이번에 안 마실 때
        dp[i][0] = max(max(dp[i - 1][1], dp[i - 1][2]), dp[i-1][0]);
        // 전 꺼 안 마시고, 이번에 마실 때
        dp[i][1] = dp[i - 1][0] + arr[i];
        // 전 꺼 마시고, 이번 것도 마실 때
        dp[i][2] = dp[i - 1][1] + arr[i];
    }
    maxsum = max(dp[n - 1][0], dp[n - 1][1]);
    maxsum = max(maxsum, dp[n - 1][2]);
    cout << maxsum;
    return 0;
}