[백준 4781] 사탕 가게 (C#, C++) - soo:bak

문제 링크

4781번 - 사탕 가게

설명

사탕 종류와 예산이 주어질 때, 각 사탕을 원하는 만큼 살 수 있는 상황에서 예산을 넘지 않으면서 얻을 수 있는 최대 칼로리를 구하는 문제입니다.

접근법

같은 사탕을 여러 개 살 수 있으므로 무한 배낭 문제입니다.

가격이 소수점 둘째 자리까지 주어지므로, 100을 곱해 센트 단위의 정수로 변환합니다. 부동소수점 오차를 방지하기 위해 0.5를 더한 뒤 정수로 변환합니다.

각 예산에 대해 얻을 수 있는 최대 칼로리를 저장하는 배열을 만듭니다. 각 사탕에 대해 해당 사탕의 가격부터 예산까지 순회하며, 현재 예산에서 사탕을 추가로 사는 경우와 사지 않는 경우 중 더 큰 값을 선택합니다. 가격을 오름차순으로 순회하기 때문에 같은 사탕을 여러 번 선택할 수 있습니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    while (true) {
      var first = Console.ReadLine()!.Split();
      var n = int.Parse(first[0]);
      var dm = double.Parse(first[1]);
      if (n == 0 && dm < 0.001) break;

      var budget = (int)(dm * 100 + 0.5);
      var cal = new int[n];
      var cost = new int[n];
      for (var i = 0; i < n; i++) {
        var line = Console.ReadLine()!.Split();
        cal[i] = int.Parse(line[0]);
        cost[i] = (int)(double.Parse(line[1]) * 100 + 0.5);
      }

      var dp = new int[budget + 1];
      for (var i = 0; i < n; i++) {
        for (var j = cost[i]; j <= budget; j++) {
          var cand = dp[j - cost[i]] + cal[i];
          if (cand > dp[j]) dp[j] = cand;
        }
      }

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

C++

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

typedef vector<int> vi;

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

  while (true) {
    int n; double dm;
    cin >> n >> dm;
    if (n == 0 && dm < 0.001) break;
    int budget = (int)(dm * 100 + 0.5);

    vi cal(n), cost(n);
    for (int i = 0; i < n; i++) {
      double p; cin >> cal[i] >> p;
      cost[i] = (int)(p * 100 + 0.5);
    }

    vi dp(budget + 1, 0);
    for (int i = 0; i < n; i++) {
      for (int j = cost[i]; j <= budget; j++)
        dp[j] = max(dp[j], dp[j - cost[i]] + cal[i]);
    }

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

  return 0;
}