31721번 - 수강신청 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 275 | 67 | 59 | 28.502% |
문제
이번 학기에 개설되는 과목들을 살펴보던 달구는 수강을 희망하는 $N$개의 과목을 추려냈다. 야망 넘치는 달구는 이번 학기에 최대한 많은 과목을 수강하고자 하며, 이에 따라 수강을 희망하는 $N$개의 과목에 대한 수강 정원 및 수강 희망자 수를 조사하였다. 그중 $i$번째 과목의 수강 정원은 $a_i$명이며, 해당 과목의 수강 희망자 수는 달구를 포함하여 $b_i$명이다.
달구가 다니는 학교의 전교생 수는 달구를 포함하여 총 $M$명이며, 각 학생은 초당 최대 한 개의 과목에만 수강신청을 할 수 있다. 이때, 여러 명의 학생이 동시에 같은 과목에 수강신청을 하더라도, 달구는 무조건 그 과목에 먼저 신청할 수 있다. 수강신청은 선착순으로 진행되며 수강 정원이 가득 찬 과목에는 더 이상 수강신청을 할 수 없다. 단, 달구가 조사한 각 과목의 수강 희망자를 제외한 학생들은 해당 과목에 수강신청을 하지 않는다.
달구는 수강신청 전에 미리 $N$개의 과목에 대해 서로 다른 우선순위를 지정해 두고, 우선순위에 따라 순서대로 각 과목에 수강신청을 하고자 한다. 만약 우선순위가 더 높은 강의의 수강 정원이 모두 찼다면 해당 과목에는 수강신청을 시도하지 않고 다음 우선순위의 과목을 신청한다. 단, 수강신청 도중 상황에 따라 과목들의 우선순위를 변경할 수는 없다.
그러나, 달구는 다른 학생들의 수강신청 순서에 따라 수강할 수 있는 과목의 수가 크게 달라질 수 있다는 사실을 깨달았다! 이에 따라, 선택할 수 있는 모든 우선순위 중 다른 학생들의 수강신청 순서의 최악의 경우에도 가장 많은 과목을 수강할 수 있도록 우선순위를 정하고자 한다. 달구를 위해 최선의 전략으로 각 과목의 우선순위를 배정했을 때 다른 학생들의 수강신청 순서가 최악인 경우에 달구가 수강할 수 있는 과목의 개수를 구해주자.
입력
첫 번째 줄에 달구가 수강을 희망하는 과목의 개수 $N$과 달구를 포함한 전교생의 수 $M$이 공백으로 구분되어 주어진다. $(1\leq N, M\leq 100\,000)$
이후 $N$개의 줄에 걸쳐, $i+1$번째 줄에 $i$번째 과목의 수강 정원 $a_i$와 달구를 포함한 수강 희망자 수 $b_i$가 공백으로 구분되어 주어진다. $(1\leq a_i, b_i\leq M)$
출력
달구가 최악의 경우에도 가장 많은 과목을 수강할 수 있도록 우선순위를 배정했을 때, 최악의 경우에 수강할 수 있는 과목의 개수를 구하여라.
예제 입력 1
3 3 2 3 2 1 3 2
예제 출력 1
3
달구가 각 과목을 $1, 3, 2$ 순서로 수강신청을 진행한다면, 다른 두 학생이 어떤 순서로 수강신청을 진행하는지와 관계 없이 반드시 모든 $3$개의 과목을 수강할 수 있다.
예제 입력 2
2 5 3 5 3 5
예제 출력 2
1
달구가 어떤 순서로 수강신청을 진행하더라도, 처음 달구가 수강신청을 진행한 과목이 아닌 다른 과목에 $5$명의 학생 중 $3$명이 몰린다면 달구는 하나의 과목만 수강할 수 있다.
예제 입력 3
3 4 1 1 3 1 2 1
예제 출력 3
3
모든 과목의 수강 희망자가 달구 혼자 뿐이므로, 달구가 모든 $3$개의 과목을 수강할 수 있다.
출처
University > UNIST-DGIST-POSTECH > 2024 UNIST-DGIST-POSTECH 연합 프로그래밍 경진대회 (2024 UDPC) > Senior Division G번
University > UNIST-DGIST-POSTECH > 2024 UNIST-DGIST-POSTECH 연합 프로그래밍 경진대회 (2024 UDPC) > Junior Division I번
University > UNIST-DGIST-POSTECH > 2024 UNIST-DGIST-POSTECH 연합 프로그래밍 경진대회 (2024 UDPC) > Open Contest J번
- 문제를 만든 사람: 99asdfg
- 문제를 검수한 사람: hyperbolic, leo020630, lky7674, mjhmjh1104, nick832, slah007, tony9402, utilforever
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호