[백준 12018] Yonsei TOTO (C#, C++) - soo:bak

문제 링크

12018번 - Yonsei TOTO

설명

마일리지 제도에 따라 주어진 마일리지로 최대 몇 개의 과목을 수강할 수 있는지 계산하는 문제입니다.

각 과목은 정원이 있으며, 수강을 원하는 사람들이 마일리지를 배분하여 경쟁하게 됩니다.

정원이 k명인 경우, 마일리지를 많이 넣은 상위 k명까지만 수강이 가능합니다.

접근법

각 과목에 대해 수강에 필요한 최소 마일리지를 먼저 계산합니다.

• 신청자가 정원보다 적다면 무조건 수강이 가능하므로, 최소 마일리지는 1로 간주합니다.
• 신청자가 정원 이상이라면, 마일리지를 내림차순 정렬하여
  정원에 해당하는 위치의 마일리지가 최소 기준이 됩니다.

이렇게 모든 과목에 대해 수강에 필요한 최소 마일리지를 구한 뒤,

이를 오름차순으로 정렬하여 마일리지가 적게 드는 과목부터 순차적으로 수강합니다.

각 과목을 수강할 때마다 해당 마일리지를 차감하며,

마일리지가 더 이상 부족해지기 전까지 수강 가능한 과목의 수를 누적합니다.

---

Code

C#

using System;
using System.Collections.Generic;
using System.Linq;

class Program {
  static void Main() {
    var parts = Console.ReadLine().Split();
    int n = int.Parse(parts[0]);
    int m = int.Parse(parts[1]);

    var pq = new List<int>();

    for (int i = 0; i < n; i++) {
      var line = Console.ReadLine().Split().ToList();
      int s = int.Parse(line[0]), k = int.Parse(line[1]);
      var scores = Console.ReadLine().Split().Select(int.Parse).ToList();
      scores.Sort((a, b) => b.CompareTo(a));

      pq.Add(s < k ? 1 : scores[k - 1]);
    }

    pq.Sort();
    int count = 0;
    foreach (var cost in pq) {
      if (m >= cost) {
        m -= cost;
        count++;
      } else break;
    }

    Console.WriteLine(count);
  }
}

C++

#include <bits/stdc++.h>

using namespace std;
typedef vector<int> vi;

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

  int n, m; cin >> n >> m;

  priority_queue<int, vi, greater<int>> pq;
  for (int i = 0; i < n; ++i) {
    int s, k; cin >> s >> k;
    vi scores(s);
    for (int& x : scores)
      cin >> x;
    if (s < k) pq.push(1);
    else {
      sort(scores.rbegin(), scores.rend());
      pq.push(scores[k - 1]);
    }
  }

  int count = 0;
  while (!pq.empty() && m > 0 && pq.top() <= m) {
    m -= pq.top();
    pq.pop();
    ++count;
  }
  cout << count << "\n";

  return 0;
}