[백준 2156] 포도주 시식 (C#, C++) - soo:bak

문제 링크

2156번 - 포도주 시식

설명

포도주 잔이 일렬로 놓여 있을 때, 연속된 세 잔을 모두 마실 수 없다는 조건에서 마실 수 있는 포도주의 최대 양을 구하는 문제입니다.

접근법

i번째 잔까지 고려했을 때의 최대값을 차례대로 구합니다. i번째 잔에 대해 가능한 경우는 세 가지입니다. i번째 잔을 마시지 않는 경우, i번째 잔만 마시는 경우, i-1번째와 i번째 잔을 연속으로 마시는 경우입니다. 이 세 경우 중 최대를 선택해 누적하면 조건을 지키면서 최댓값을 구할 수 있습니다.

처음 몇 잔은 따로 초기값을 잡고, 이후에는 같은 방식으로 갱신합니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    int n = int.Parse(Console.ReadLine()!);
    int[] a = new int[n + 1];
    for (int i = 1; i <= n; i++)
      a[i] = int.Parse(Console.ReadLine()!);

    if (n == 1) {
      Console.WriteLine(a[1]);
      return;
    }

    int[] dp = new int[n + 1];
    dp[1] = a[1];
    dp[2] = a[1] + a[2];

    for (int i = 3; i <= n; i++) {
      int c1 = dp[i - 1];
      int c2 = dp[i - 2] + a[i];
      int c3 = dp[i - 3] + a[i - 1] + a[i];
      dp[i] = Math.Max(c1, Math.Max(c2, c3));
    }

    Console.WriteLine(dp[n]);
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

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

  int n; cin >> n;
  vector<int> a(n + 1), dp(n + 1, 0);
  for (int i = 1; i <= n; i++)
    cin >> a[i];

  if (n == 1) {
    cout << a[1] << "\n";
    return 0;
  }

  dp[1] = a[1];
  dp[2] = a[1] + a[2];

  for (int i = 3; i <= n; i++) {
    int c1 = dp[i - 1];
    int c2 = dp[i - 2] + a[i];
    int c3 = dp[i - 3] + a[i - 1] + a[i];
    dp[i] = max(c1, max(c2, c3));
  }

  cout << dp[n] << "\n";

  return 0;
}