[BOJ]12018: Yonsei TOTO

chellchell·2020년 9월 6일

BOJ

목록 보기

2/6

문제

12018: Yonsei TOTO

문제

연세대학교 수강신청이 얼마 전부터 바뀌어, 마일리지 제도로 바뀌었다. 이 제도는 각각의 학생들에게 마일리지를 주어 듣고 싶은 과목에 마일리지를 과목당 1~36을 분배한다. 그리고 모두 분배가 끝이 나면 과목에 대해서 마일리지를 많이 투자한 순으로 그 과목의 수강인원만큼 신청되는 방식이다.
성준이는 연세대학교 재학 중인 학생이다. 성준이는 저번 수강신청에서 실패하여 휴학을 했기 때문에 이번 수강신청만은 필사적으로 성공하려고 한다. 그래서 성준이는 학교 홈페이지를 뚫어버렸다.
그 덕분에 다른 사람들이 신청한 마일리지를 볼 수 있게 되었다. 성준이는 주어진 마일리지로 최대한 많은 과목을 신청하고 싶어 한다. (내가 마일리지를 넣고 이후에 과목을 신청하는 사람은 없다) 마일리지는 한 과목에 1에서 36까지 넣을 수 있다.

입력

첫째 줄에는 과목 수 n (1 ≤ n ≤ 100)과 주어진 마일리지 m (1 ≤ m ≤ 100)이 주어진다. 각 과목마다 2줄의 입력이 주어지는데 첫째 줄에는 각 과목에 신청한 사람 수 Pi과 과목의 수강인원 Li이 주어지고 그 다음 줄에는 각 사람이 마일리지를 얼마나 넣었는지 주어진다. (1 ≤ Pi ≤100, 1 ≤ Li ≤ 100)
(단 마일리지가 같다면 성준이에게 우선순위가 주어진다고 하자.)

출력

첫째 줄에 주어진 마일리지로 최대로 들을 수 있는 과목 개수를 출력한다.

예제 입력
5 76
5 4 
36 25 1 36 36
4 4
30 24 25 20
6 4
36 36 36 36 36 36
2 4
3 7
5 4
27 15 26 8 14
예제 출력
4

풀이방법

각 과목별로 신청한 학생들의 마일리지를 배열에 저장한 다음 내림차순 정렬을 해준다. 내림차순 정렬한 배열에서 수강가능한 마지막 번째 학생의 마일리지를 다른 배열에 따로 저장해둔다. 수강가능한 마지막 번째 학생이 가장 과목을 수강할 수 있는 가장 최소의 마일리지를 입력했기 때문이다. 최소의 마일리지를 누적하여 최대의 과목을 수강하는 이 문제 풀이의 전략이다. 다른 배열에 저장할 때 유의해야할 점은 입력가능한 마일리지의 최소가 1이라는 점이다. 새로운 배열에 모두 저장이 되면 오름차순 정렬하여 기준 마일리지를 초과하면 결과를 반환한다.

코드

#include <iostream>
#include <algorithm>
#pragma warning(disable:4996)
using namespace std;
int main() {
	int n, m;
	int p, l;
	int j,i;
	int sum[101] = { 0, };
	int count = 0,ret=0;
	int arr[101][101] = { 0, };

	scanf("%d %d", &n, &m);
	for (i = 0; i < n; i++) {
		scanf("%d %d", &p, &l);
		for (j = 0; j < p; j++) {
			scanf("%d", &arr[i][j]);
		}
		if (p < l)
			sum[i] = 1;
		else {
			sort(arr[i], arr[i] + p, greater<int>());
			sum[i] = arr[i][l - 1];
		}
	}

	sort(sum, sum + n, less<int>());

	for (i = 0; i < n; i++) {
		if ((count+sum[i])> m)
			break;
		count += sum[i];
		ret+=1;
	}
	printf("%d\n", ret);
}