[백준 24303] ПРЪЧКИ (C#, C++) - soo:bak

문제 링크

24303번 - ПРЪЧКИ

설명

길이와 개수가 제한된 막대를 이어 붙여 총 길이가 L 이상이 되도록 할 때 필요한 최소 개수를 구하는 문제입니다.

접근법

사용할 막대 개수가 최대 297개이므로, 각 길이를 만들기 위한 최소 개수를 동적 프로그래밍으로 계산합니다.

이후 각 막대를 개수만큼 반영하고, 목표 길이 이상이 되는 경우 중 최소 개수를 답으로 출력합니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    var parts = Console.ReadLine()!.Split();
    var a = new int[3];
    var b = new int[3];
    for (var i = 0; i < 3; i++)
      a[i] = int.Parse(parts[i]);
    for (var i = 0; i < 3; i++)
      b[i] = int.Parse(parts[3 + i]);
    var l = int.Parse(parts[6]);

    var total = a[0] * b[0] + a[1] * b[1] + a[2] * b[2];
    var inf = 1_000_000;
    var dp = new int[total + 1];
    for (var i = 1; i <= total; i++)
      dp[i] = inf;

    for (var t = 0; t < 3; t++) {
      var len = a[t];
      var cnt = b[t];
      for (var i = 0; i < cnt; i++) {
        for (var s = total; s >= len; s--) {
          if (dp[s - len] + 1 < dp[s]) dp[s] = dp[s - len] + 1;
        }
      }
    }

    var ans = inf;
    for (var s = l; s <= total; s++) {
      if (dp[s] < ans) ans = dp[s];
    }

    Console.WriteLine(ans == inf ? 0 : ans);
  }
}

C++

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

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

  int a[3], b[3];
  for (int i = 0; i < 3; i++)
    cin >> a[i];
  for (int i = 0; i < 3; i++)
    cin >> b[i];
  int L; cin >> L;

  int total = a[0] * b[0] + a[1] * b[1] + a[2] * b[2];
  const int inf = 1000000;
  vector<int> dp(total + 1, inf);
  dp[0] = 0;

  for (int t = 0; t < 3; t++) {
    int len = a[t];
    int cnt = b[t];
    for (int i = 0; i < cnt; i++) {
      for (int s = total; s >= len; s--) {
        if (dp[s - len] + 1 < dp[s]) dp[s] = dp[s - len] + 1;
      }
    }
  }

  int ans = inf;
  for (int s = L; s <= total; s++) {
    if (dp[s] < ans) ans = dp[s];
  }

  cout << (ans == inf ? 0 : ans) << "\n";

  return 0;
}