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

2156번: 포도주 시식 (acmicpc.net)

2156번: 포도주 시식

문제 설명은 다음과 같다.

문제 설명 / 입력 / 출력

예제 입력 / 예제 출력

 

아주 기본적인 DP 문제이다. 틀려서는 안된다고 생각했지만, 1트에 틀려서 2트째에 정답을 맞았다.

 

내가 처음 트라이할 때 냈던 코드에 빠져 있었던 사고들을 공유하기도 하고 기록해 둘겸 작성하려고 한다.

 

우선 내가 생각한 방법은 다음과 같다.

• n번째 포도주를 마시는 경우와 마시지 않는 경우가 존재한다.
• n번째 포도주를 마시는 경우에는 다음의 두 가지 경우가 다시 존재한다.
  • n-3번째 포도주까지 마신 양 + n-1번째 포도주의 양 + n번째 포도주의 양
  • n-2번째 포도주까지 마신 양 + n번째 포도주의 양
• n번째 포도주를 마시지 않는 경우는 다음의 경우이다.
  • n-1번째 포도주까지 마신 양 = n번째 포도주까지 마신 양

잘 생각해보면 위의 3가지 경우가 통틀어 다라는 것을 알 수 있다.

즉, dp[n] 배열을 만들어서 cout << dp[n] 해주면 끝난다는 것이다.

 

아래는 제출한 C++ 코드이다.

#include <algorithm>
#include <iostream>
#define fastcpp ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
int n;
int grape[10001];
int dp[10001];
int main() {
    fastcpp;
    cin >> n;
    for (int i=1;i<=n;i++) cin >> grape[i];
    dp[1] = grape[1];
    dp[2] = grape[1]+grape[2];
    for (int i=3;i<=n;i++){
        dp[i] = max({dp[i-1],dp[i-3]+grape[i-1]+grape[i], dp[i-2]+grape[i]});
    }
    cout << dp[n];
    return 0;
}