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

문제 링크 : https://boj.kr/2156

이 문제에서는 연속된 인접 포도주가 최대 2잔까지 허용된다.

이 문제에서의 핵심은 포도주를 마시기 위해선 인접한 최대 2개의 노드를 비교했을때 마신 포도주의 위치가 2 이하여야 하는 것이다.

포도주를 마신 위치를 1로 하고 안 마신 위치를 0으로 표현하였다.

현재 위치를 기준으로 그 이전 단계를 계산한다면 아래의 경우를 생각할 수 있다.

1. 현재 포도주를 먹지 않았을 경우

 - 그 앞에 어떤 경우가 와도 상관 없다. 마신경우, 최대 2개까지만 허용 (0+0, 1+0, 1+1+0)

2. 현재 포도주를 먹었을 경우

 - 바로 전 포도주를 먹지 않았을 수도 있다. (0+1)

 - 바로 전(-1) 포도주를 먹었다면 반드시 그 이전(-2) 포도주는 먹지 않았어야 한다. (0+1+1)

여기서 메모이제이션을 할 수 있는 공통 요소를 찾을 수 있다.

1. (0+0, 1+0, 1+1+0)

2. (0+1, 0+1+1)

조건1에서 빨간 부분과 조건2에서의 빨간 부분이 서로 같은 값을 가짐을 확인할 수 있다.

따라서 앞선 단계(N-1)에서 했던 조건2의 연산을 조건1의 앞 부분에 연결해서 사용이 가능하다는 의미가 된다.

1. (0+0, DP[N-1][1]+0) 로 바꿀 수 있다.

* DP[N][C]에서 N은 단계, C는 포도주를 마셨는지 여부를 의미하며 가능한 모든 경우 중에서의 최대값을 저장한다.

또한, 0+0을 살펴보면 1의 이전 단계를 의미하기도 한다.

따라서 1. (DP[N-1][0]+0, DP[N-1][1]+0)으로 표현이 가능하다.

이 문제에서의 핵심은 포도주를 먹지 않았을 경우의 위상(0)이다.

1의 경우를 다시 살펴보면

1. (0+0, 1+0, 1+1+0)

모두 0으로 끝나는 것이 핵심이다.

즉, 1의 조건으로 끝난 경우 이 뒤에는 1의 조건을 다시 붙이던 2의 조건을 붙이던 상관이 없다는 뜻이다.

이어서 계속 풀어보면,

1. (DP[N-1][0], DP[N-1][1])

2. (0+1, 0+1+1)

앞서 말한 것처럼 1의 조건으로 끝나는(0에 해당하는 부분)을 대치시켜 준다.

1. (DP[N-1][0], DP[N-1][1])

2. (DP[N-1][0]+wine[N], DP[N-2][0]+wine[N-1]+wine[N])

조건1의 케이스에선 마신 상태(1)를 DP[N][1]로 대치하였었는데 그 이유는 DP[N-1][1] + 0 으로 반드시 뒤에 0이 오는 상태라서 그 뒤에 아무거나 다 붙일 수 있기 때문에 DP로 대치를 한 것이다.

하지만, 조건2에선 1로 끝나는 상태이기 때문에 그 뒤에 아무거나 오게 된다면 조건에 위배되기 때문에 DP로 대치할 수 없는 것이다.

// BOJ 2156 포도주 시식
#include <bits/stdc++.h>
 
using namespace std;
 
#define MAXN 10001
int wine[MAXN];
int dp[MAXN][2]; //[0] 안선택 [1] 선택
 
int max(int a, int b) {
    return a > b ? a : b;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("../input.txt", "r", stdin);
 
    int num;
    cin >> num;
 
    for (int i = 1; i <= num; i++)
        cin >> wine[i];
 
    dp[1][1] = wine[1]; // 초기 기저
    for (int i = 2; i <= num; i++) {
        // DP[?]의 의미는 마지막 state가 ?로 끝난다는 뜻
        // DP[0]+0 / DP[1]+0
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
        // DP[0]+1 / DP[0]+1+1
        dp[i][1] = max(dp[i - 1][0], dp[i - 2][0] + wine[i - 1]) + wine[i];
    }
    cout << max(dp[num][0], dp[num][1]);
 
    return 0;
}

유사 풀이법으로 3개의 DP를 비교하는 방법이 있다.

DP,0 / DP,0,1 / DP,0,1,1 의 케이스 중 최대 값을 취한다.

이 경우 DP에 해당하는 부분엔 어떠한 경우가 와도 상관 없고 DP를 2차원 배열로 선언할 필요도 없다.

여기서 한가지 유심히 확인할 수 있는 부분은 DP가 항상 0 앞에 온다는 것이다.

0을 기준으로 구분한다는 규칙은 변함이 없다.

// BOJ 2156 포도주 시식
#include <bits/stdc++.h>
 
using namespace std;
 
#define MAXN 10001
int wine[MAXN];
int dp[MAXN];
 
int max(int a, int b) {
    return a > b ? a : b;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("../input.txt", "r", stdin);
 
    int num;
    cin >> num;
 
    for (int i = 1; i <= num; i++)
        cin >> wine[i];
 
    dp[1] = wine[1]; // 초기 기저
    dp[2] = wine[1] + wine[2]; // 초기 기저
    for (int i = 3; i <= num; i++)
                   // DP[-1]+0,        DP[-2]+0+1,              DP[-3]+0+1+1
        dp[i] = max(dp[i - 1], max(dp[i - 2] + wine[i], dp[i - 3] + wine[i - 1] + wine[i]));
    cout << dp[num];
 
    return 0;
}