[백준] 2156번 포도주 시식

March 14, 2021 ( last updated : March 14, 2021 )
dp 알고리즘 algorithm

https://github.com/sneakstarberry/

Abstract

[백준] 2156번 포도주 시식

[백준] 2156번 포도주 시식

백준 2156번

dp문제 중 하나입니다. 해당 문제는 브루트 포스로도 풀 수 있지만 시간상 최적화를 해야하는 문제 입니다. 따라서 문제에서 최적해를 찾을 수 있는 공식을 찾아야합니다.
포도주는 3번 연속으로 마실 수 없으니 다음과 같이 생각할 수 있습니다. 마지막 포도주를 마신다고 하였을 때

  1. 마지막 이전의 포도주를 마신다.

    dp[n] = arr[n] + arr[n-1] + dp[n-3]
    마지막에 연달아 마셨으므로 마지막에서 뒤로 세번째 포도주는 마실 수 없습니다. 따라서 4번째 까지 마셨을 때 최대 값(dp[n-3])을 더해주는 것입니다.

  2. 마지막 이전의 포도주를 마시지 않는다.

    dp[n] = arr[n] + dp[n-2]
    마지막 포도주만 마셨으므로 마지막에서 뒤로 세번째 포도까지 마셨을 때의 최대값(dp[n-2])을 더해주면 됩니다.

하지만 잘 생각해 보았을 때 마지막 포도주를 마실 수도 있고 혹은 마지막 포도주를 안마실 수도 있습니다. 그렇기 때문에 마지막 포도주까지 마셨을 때와 안마셨을 때를 비교해서 더 높은 값을 결정합니다.

dp[n] = max(dp[n], dp[n-1])

이를 통해서 우리는 최대 값을 구할 수 있게 되었습니다.

#include <algorithm>
#include <iostream>

using namespace std;
// dp[n] = dp[n-3] + array[n] + array[n-1];
// dp[n] = dp[n-2] + array[n];
int N, DP[10001], ARR[10001];

int main() {
  cin >> N;

  for (int i = 1; i <= N; i++) {
    cin >> ARR[i];
  }
  DP[1] = ARR[1];
  DP[2] = ARR[1] + ARR[2];

  for (int i = 3; i <= N; i++) {
    DP[i] = max(DP[i - 3] + ARR[i] + ARR[i - 1], DP[i - 2] + ARR[i]);
    DP[i] = max(DP[i], DP[i - 1]);
  }
  cout << DP[N];

  return 0;
}

Originally published March 14, 2021
Latest update March 14, 2021

Related posts :

{# #}