[C++] 백준 12018번: Yonsei TOTO

문제 링크

12018번: Yonsei TOTO

문제 요약

주어진 마일리지로 수강신청을 한다. 과목별로 일정한 마일리지를 할당할 수 있다. 각 과목의 신청 인원 중 제한된 수강인원 수만큼, 마일리지가 높은 순서대로 과목을 수강할 수 있다. 성준이가 수강신청을 하고자 할때, 들을 수 있는 최대 과목 수를 구해야 한다. (단, 마일리지가 같은 경우, 성준이가 우선권을 가진다.)

접근 방법

유명한 연세대학교의 수강신청과 관련된 문제입니다.

그리디하게 접근할 수 있습니다. 먼저 각 과목을 들기 위해 필요한 마일리지의 최솟값을 모두 구해야 합니다. 그리고 그 최솟값들을 정렬한 뒤에, 필요한 마일리지가 작은 과목부터 순서대로 고르면 됩니다.

마일리지의 최솟값을 구하는 방법은 간단합니다. 두 가지 경우가 존재할 수 있습니다.

1. 수강인원이 신청한 사람 수보다 큰 경우
2. 그 외의 경우

1번인 경우에는 그냥 1 마일리지만 넣어도 해당 과목을 수강할 수 있습니다.

그 외의 경우에는 신청한 마일리지를 내림차순으로 정렬했을 때, 해당 과목을 들을 수 있는 마지막 사람과 같은 마일리지를 넣는 것이 최소비용이 됩니다. i번째 과목을 신청한 사람을 $P_i$, i번째 과목의 수강인원을 $L_i$라고 했을 때, 신청한 마일리지를 내림차순으로 정렬하면 인덱스가 $(P_i-L_i)$인 원소가 최소비용이 됩니다.

코드

#include <bits/stdc++.h>

using namespace std;

int main(void)
{
	int n, m;
	cin >> n >> m;

	vector<int> point;
	for (int i = 0; i < n; i++)
	{
		int p, l;
		cin >> p >> l;

		vector<int> v(p);
		for (int j = 0; j < p; j++)
			cin >> v[j];

		if (p < l)
			point.push_back(1);
		else
		{
			sort(v.begin(), v.end());
			point.push_back(v[p - l]);
		}
	}

	sort(point.begin(), point.end());

	int cnt = 0;
	for (auto& i : point)
	{
		if (m >= i)
		{
			cnt++;
			m -= i;
		}
	}

	cout << cnt;
	return 0;
}