boj, 백준) 12018. Yonsei TOTO (C/C++)

1. 문제 링크

https://www.acmicpc.net/problem/12018

12018번: Yonsei TOTO

 

2. 문제 개요

과목 신청을 위해 마일리지를 1~36점까지 분배할 수 있다. 모두 분배가 끝나면 과목에 대해서 마일리지를 많이 투자한 순으로 그 과목의 수강인원만큼 신청되는 방식이다.

 

과목수, 마일리지, 각 과목마다 수강인원, 신청인원 등이 주어진다고 했을 때, 주어진 마일리지로 최대로 들을 수 있는 과목 개수를 출력하는 프로그램을 작성하자.

 

3. 문제 힌트

각 과목에서 비용(마일리지)을 아끼는 것에서 시작해서 전체로 넓혀간다고 생각해보자.

 

어떠한 한 과목을 어떻게 하면 최소한의 마일리지를 사용해서 수강 신청할 수 있을까?

이러한 것을 전체에 대해서 수행한 뒤 어떤 과목들을 골라야 최대로 들을 수 있을까?

 

4. 문제 풀이

다른 DP문제 같이 수학적으로 최적이라는 것을 표현할 수 있으면 좋으나 Greedy는 대부분 감..?!에서 출발하는 것 같다.

 

우선, 주어진 과목에 대해서 적어도 얼마의 마일리지를 투자해야 수강할 수 있는지 생각해보자.

 

5명 신청했고, 4명 뽑을 수 있는 과목 A 가 현재 다른학생이

36 25 1 36 36의 마일리지를 투자한 상태라고 해보자.

여기서 36, 36, 36, 25, 1로 정렬하고 적어도 4등 이내로 들어야 함을 의미한다. 그 말은 적어도 25 이상은 투자해야 함을 의미한다.

 

이렇게 과목 A는 25를 투자하면 수강할 수 있다.

이 방법을 모든 과목에 사용해보자.

 

각 과목마다 수강할 수 있는 마일리지의 최솟값을 구하면 최소 힙에 Push 해두자.

왜냐하면 마일리지가 최소로 드는 과목을 선택해나가야지 주어진 마일리지에서 과목의 수를 최대로 할 수 있고, 이게 당연하기 때문이다.

5. 코드

 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

int n, m;
priority_queue<int, vector<int>, greater<int>> pq;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;

	while (n--)
	{
		int p, l;
		cin >> p >> l;

		vector<int> v(p);

		for (int i = 0; i < p; ++i)
			cin >> v[i];
		
		sort(v.begin(), v.end());

		if (v.size() < l)
			pq.push(1);
		else
			pq.push(v[p-l]);
	}

	int sum = 0;
	int ans = 0;
	while (!pq.empty() && sum + pq.top() <= m)
	{
		sum += pq.top();
		++ans;
		pq.pop();
	}

	cout << ans;

	return 0 ;
}

 

6. 결과