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

문제 링크

16194번 - 카드 구매하기 2

설명

1장짜리, 2장짜리, … N장짜리 카드팩이 각각 있고 가격이 다릅니다.

카드를 정확히 N장 사는 데 드는 최소 금액을 구하는 문제입니다.

접근법

카드 i장을 사는 최소 금액을 구할 때, 마지막에 어떤 팩을 샀는지로 나눠 생각합니다.

예를 들어 5장을 사려면, 마지막에 1장짜리 팩을 사고 나머지 4장의 최소 금액을 더할 수도 있고, 2장짜리 팩을 사고 나머지 3장의 최소 금액을 더할 수도 있습니다.

이렇게 1장짜리부터 i장짜리 팩까지 모두 시도해보고, 그중 가장 싼 경우를 선택합니다.

1장부터 N장까지 차례로 계산하면, N장을 사는 최소 금액을 구할 수 있습니다.

---

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++) {
      dp[i] = price[i];
      for (var j = 1; j <= i; j++) {
        var candidate = dp[i - j] + price[j];
        if (candidate < dp[i]) dp[i] = candidate;
      }
    }

    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++) {
    dp[i] = price[i];
    for (int j = 1; j <= i; j++) {
      int candidate = dp[i - j] + price[j];
      if (candidate < dp[i]) dp[i] = candidate;
    }
  }

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

  return 0;
}