[백준 11052] 카드 구매하기 (C#, C++) - soo:bak

문제 링크

11052번 - 카드 구매하기

설명

1장짜리부터 N장짜리까지 카드팩의 가격이 주어질 때, 카드를 정확히 N장 사면서 지불 금액을 최대로 만드는 문제입니다.

접근법

카드 1장을 살 때의 최대 금액부터 차례로 구해나갑니다.

카드 i장을 사는 방법은 여러 가지입니다. 마지막에 1장짜리 팩을 샀다면 나머지 i-1장의 최대 금액에 1장짜리 가격을 더한 것이고, 마지막에 2장짜리 팩을 샀다면 i-2장의 최대 금액에 2장짜리 가격을 더한 것입니다.

이런 식으로 마지막에 산 팩의 크기를 1부터 i까지 모두 시도해보고 그중 가장 큰 값을 선택합니다.

---

Code

C#

using System;

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

    var dp = new int[n + 1];
    for (var i = 1; i <= n; i++) {
      for (var j = 1; j <= i; j++)
        dp[i] = Math.Max(dp[i], dp[i - j] + price[j]);
    }

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

C++

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

typedef vector<int> vi;

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

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

  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= i; j++)
      dp[i] = max(dp[i], dp[i - j] + price[j]);
  }

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

  return 0;
}