[백준 9784] Boiled Eggs (C#, C++) - soo:bak

문제 링크

9784번 - Boiled Eggs

설명

한 번 끓이는 데 15분이므로 여러 번 끓일 수 없습니다. 따라서 한 번에 넣을 계란을 골라야 합니다. 최대 P개까지만 넣을 수 있고, 총 무게가 Q 이하여야 하며, 가장 많은 계란을 끓이는 최대 개수를 구하는 문제입니다.

접근법

먼저 무게 배열을 오름차순으로 정렬합니다.

다음으로 가벼운 것부터 순서대로 더하며 개수와 무게를 누적합니다. 개수가 P를 넘거나 무게가 Q를 초과하면 중단합니다.

이후 누적된 개수가 최대 개수가 됩니다.

시간 복잡도는 O(n log n)입니다.

---

Code

C#

using System;
using System.Linq;
using System.Text;

class Program {
  static void Main() {
    var t = int.Parse(Console.ReadLine()!);
    var sb = new StringBuilder();
    for (var tc = 1; tc <= t; tc++) {
      var p1 = Console.ReadLine()!.Split().Select(int.Parse).ToArray();
      var n = p1[0];
      var p = p1[1];
      var q = p1[2];
      var eggs = Console.ReadLine()!.Split().Select(int.Parse).OrderBy(x => x).ToArray();

      var cnt = 0;
      var w = 0;
      foreach (var e in eggs) {
        if (cnt == p)
          break;
        if (w + e > q)
          break;
        w += e;
        cnt++;
      }
      sb.Append("Case ").Append(tc).Append(": ").Append(cnt).Append('\n');
    }
    Console.Write(sb);
  }
}

C++

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

typedef vector<int> vi;

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

  int t;
  cin >> t;
  for (int tc = 1; tc <= t; tc++) {
    int n, p, q;
    cin >> n >> p >> q;
    vi a(n);
    for (int i = 0; i < n; i++)
      cin >> a[i];
    sort(a.begin(), a.end());

    int cnt = 0, w = 0;
    for (int x : a) {
      if (cnt == p)
        break;
      if (w + x > q)
        break;
      w += x;
      cnt++;
    }

    cout << "Case " << tc << ": " << cnt << "\n";
  }

  return 0;
}