[백준] 12018번 - Yonsei TOTO (C++)

문제

연세대학교 수강신청이 얼마 전부터 바뀌어, 마일리지 제도로 바뀌었다. 이 제도는 각각의 학생들에게 마일리지를 주어 듣고 싶은 과목에 마일리지를 과목당 1~36을 분배한다. 그리고 모두 분배가 끝이 나면 과목에 대해서 마일리지를 많이 투자한 순으로 그 과목의 수강인원만큼 신청되는 방식이다.

성준이는 연세대학교 재학 중인 학생이다. 성준이는 저번 수강신청에서 실패하여 휴학을 했기 때문에 이번 수강신청만은 필사적으로 성공하려고 한다. 그래서 성준이는 학교 홈페이지를 뚫어버렸다.

그 덕분에 다른 사람들이 신청한 마일리지를 볼 수 있게 되었다. 성준이는 주어진 마일리지로 최대한 많은 과목을 신청하고 싶어 한다. (내가 마일리지를 넣고 이후에 과목을 신청하는 사람은 없다) 마일리지는 한 과목에 1에서 36까지 넣을 수 있다.

---

입력

첫째 줄에는 과목 수 n (1 ≤ n ≤ 100)과 주어진 마일리지 m (1 ≤ m ≤ 100)이 주어진다. 각 과목마다 2줄의 입력이 주어지는데 첫째 줄에는 각 과목에 신청한 사람 수 Pi과 과목의 수강인원 Li이 주어지고 그 다음 줄에는 각 사람이 마일리지를 얼마나 넣었는지 주어진다. (1 ≤ Pi ≤100, 1 ≤ Li ≤ 100)

(단 마일리지가 같다면 성준이에게 우선순위가 주어진다고 하자.)

---

출력

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

---

예제 입력 1 복사

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

예제 출력 1 복사

4

---

풀이과정

문제에 접근하는 방식은 크게 어렵지않았다.

문제로 주어진 조건들을 그대로 코드로 옮길 수 있으면 대략적인 코드구현방식은 생각할 수 있었고, 세부적으로 어떻게 로직을 구성해야

효율적으로 코드가 돌아갈 수 있느냐를 생각했을때 수강인원들의 마일리지를 정렬시켜서 내가 비교시켜야하는 값을 뽑아오고 그 값들을 모와 정렬시킨다음 작은값부터 마일리지를 차감하는 방식으로 구현을 하니 크게 어렵지않게 진행할 수 있었다.

code

#include <iostream>
#include <algorithm>
#include <vector>

int		main()
{
	int n, m, p, l, temp, count;
	std::vector <int> v, v_temp;

	std::cin >> n >> m;
	for(int i = 0; i < n; i++)
	{
		std::cin >> p >> l;
		for(int j = 0; j < p; j++) {
			std::cin >> temp;
			v_temp.push_back(temp);
		}
		std::sort(v_temp.begin(), v_temp.end());
		if (l - p > 0) v.push_back(1);
		else v.push_back(v_temp[p - l]);
		v_temp.clear();
	}
	std::sort(v.begin(), v.end());
	count = 0;
	for(int i = 0; i < v.size(); i++) {
		if (m >= v[i]) {
			m = m - v[i];
			count++;
		}
	}
	std::cout << count;
	
	return (0);
}

 

---

후기

큰틀을 짜는 과정이 크게 어려운로직은 아니였던거같아서 금방풀었었다.