[백준 12018번] : Yonsei TOTO 파이썬 풀이

Yonsei TOTO 성공

 

실버3

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	5297	1892	1580	34.909%

 

문제

연세대학교 수강신청이 얼마 전부터 바뀌어, 마일리지 제도로 바뀌었다. 이 제도는 각각의 학생들에게 마일리지를 주어 듣고 싶은 과목에 마일리지를 과목당 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

​

정렬을 활용하여 풀 수 있는 그리디 알고리즘 문제이다.

​

최대한 많은 과목을 수강신청 하기 위해서는, 수강신청에 필요한 '가장 적절한 가격' 에 해당 과목을 입찰하는 것이 중요할 것이다.

예를 들어 5명이 신청한 과목에서 4명을 뽑는다고 가정하고, 36 25 1 36 36 과 같이 사람들이 신청했다고 가정하자.

포인트가 높은 순으로 정렬(내림차순)하면 36,36,36,25,1 과 같이 되는데, 마일리지를 높게 신청한 학생 순서대로 우선순위를 부여해서 수강신청을 해주기 때문에 위 데이터에서 4명을 뽑는다면 36,36,36,25 의 마일러지를 신청한 사람들이 과목을 가져갈 것이다.

​

문제의 조건을 살펴보면 같은 마일리지로 신청하였다면 성준이에게 우선순위가 주어지기 때문에 위 과목을 가져가기 위한 가장 적절한 가격은 25마일리지가 될 것이다.

​

두번째 경우, 신청한 사람들보다 뽑는 사람이 많다고 가정해보자.

예를 들어 4명까지 수강신청이 가능한데 3명의 사람이 신청했다고 한다면, 굳이 높은 마일리지로 입찰할 필요 없이 최소 마일리지인 1마일리지만 사용해도 해당 과목을 가져갈 수 있을것이다.

​

위와 같은 논리로 모든 과목에 대해서 사람들의 마일리지 입찰 데이터를 내림차순으로 정렬한 뒤, 위에서부터 L번째 순번의 가격을 과목을 수강하는데 필요한 최소 마일리지로 책정하여 기록한다.

​

가능한 한 많은 과목을 보유중인 마일리지 내에서 수강하는 것이 최종 목표이므로, 과목을 가져가는데 필요한 마일리지 데이터를 오름차순 정렬한 뒤, 앞에서부터 포인트가 허락하는 한 과목을 수강신청하면 문제를 해결 할 수 있다.

​

위 이론을 적용한 코드는 아래와 같다.

​

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

# 목표 : 최대한 많은 과목을 듣는것
# 수강권을 얻는 방법 => 많이 투자한 순에서 해당 과목의 수강신청 인원만큼 받아줌
# => 가장 적절한 값으로 수강에 성공하는 것이 중요
# 
# 아이디어 : 다른 사람들이 입력한 가격을 내림차순으로 정렬
# 정렬한 가격들 중에서, 수강신청 인원의 마지막에 들어가는 것이 가장 적절한 가격
# 가장 이득을 보는 가격을 과목 가격 배열에 삽입
# 과목 가격 배열을 오름차순으로 정렬하고 앞에서부터 차례로 포인트가 만족하는한 과목을 담으면 된다.

import sys
input = sys.stdin.readline

n,m = map(int,input().split()) # 과목 수, 보유중인 마일리지 양

subject_price = [1]*n

for i in range(n):
    p,l = map(int,input().split()) # 신청한 사람 수,과목의 수강 인원
    data = list(map(int,input().split()))
    # 수강 가능 인원이 신청자 보다 많을 경우 => 1원만 입력해도 입찰이 가능
    if p<l:
        continue # 넘어감 => 1원
    data.sort(reverse=True) # 내림차순 정렬 => 위에서부터 컷
    # 적정 가격은 l-1번째 사람이 입찰한가격과 같은 값(같은 값이면 우선순위가 높으므로)
    subject_price[i] = data[l-1]

# 몇과목을 수강할 수 있는지 계산
count = 0 # 들을 수 있는 가격의 수
subject_price.sort()
for price in subject_price:
    if m-price >= 0: # 현재 마일리지에서 수강 가능하면
        count+=1 # 수강가능
        m-=price # 수강하기
    else:
        break # 더이상 못듣는다면 탐색 종료
print(count)

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

12018번: Yonsei TOTO