백준 [2156] "포도주 시식"

DP를 이용해서 해결하는 문제이다. 4개 반례를 성공해 의심없이 제출했는데 문제 내 함정이 있었다. 일정이 비어있다고 무조건 그날 상담을 진행할 필요는 없던 것이다. DP 식을 만드는데 실패하여 답을 찾아봤다.

아래 그림은 내가 이해한 것을 바탕으로 식을 재구성 한 것으로 파랑색 별(오늘) 가장 높은 상담 결과를 얻기 위해서는 세가지 방식이 필요했다.

1 번째 날 상담X, 2번째 날 상담X, 3번째 날 상담X

예시로 1 번째 날 상담 기록을 갖지 않고 최고 상담 기록을 얻을려면 첫번째 날 기준 전날 최고 상담 기록이 필요하기에 1 번째 날 기록을 사용하지 않은 날에는 그전 DP 기록을 가져오는 것을 확인할 수 있고 나머지 모두 동일하다.

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;
int n;
int table[10001];
int dp[10001];

// 바로 다음잔을 고르거나 다다음 잔을 고르거나

void dynamic() {
    dp[0] = 0;
    dp[1] = table[1];
    dp[2] = table[1] + table[2];
    for (int i = 3; i <= n; i++) {
        dp[i] = max({ dp[i - 3] + table[i - 1] + table[i], dp[i - 2] + table[i], dp[i - 1] });
    }
    cout << dp[n] << endl;
}

int main() {
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

    cin >> n;

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

    dynamic();
   
    return 0;

}