[BOJ] 12018번 Yonsei TOTO

[BOJ] 12018번 Yonsei TOTO 문제

꽤 쉬운 그리디 알고리즘이다. 연세 토토(또는 카지노)를 안다면 더 쉽게 풀 수 있다.

---

난 15학번이라 본격적인 토토는 2016년부터 했다

연세 카지노는 2015년부터 열린 유서 짧은 수강신청 방법이다.

기존의 수강신청과 다르게 오직 마일리지 배팅만으로 수강신청과 기타 우선순위 등을 고려해 수강 합불이 결정된다.

서버 터질 걱정도 없고 기간 내에만 배팅하면 된다는 압도적인 장점은 있었으나, 정작 인원이 많고 강의가 적었던 학부에서는 일부 학생이 우주 공강이 되어버려 휴학까지 하는 지옥이 펼쳐졌다. 이는 현재까지 보완이 계속 진행되었지만 여전히 문제라고 한다.

이젠 내겐 있어서 다 옛말이지만... 그립긴하다.

---

핵심은 수강 인원보다 배팅한 사람이 적으면 1만 넣으면 되고, 그렇지 않다면 총 배팅한 사람 중 가장 적은 마일리지로 통과하는 사람의 마일리지(즉, sort된 마일리지 중 $ L_i $번째 마일리지)를 쓰면 된다는 것이다. 마일리지가 같은 경우 성준이의 우선순위가 높다는 것을 이용해야 문제가 풀린다.

import sys

if __name__ == '__main__':
    n, m = map(int, sys.stdin.readline().rstrip().split())
    least_toto = list()
    for _ in range(n):
        P, L = map(int, sys.stdin.readline().rstrip().split())
        now_toto = list(map(int, sys.stdin.readline().rstrip().split()))
        now_toto.sort(reverse=True)
        if P >= L:
            least_toto.append(now_toto[L-1])
        else:
            least_toto.append(1)

    least_toto.sort()
    toto_count, ans = 0, 0
    for now_least_toto in least_toto:
        toto_count += now_least_toto
        if toto_count > m:
            break
        ans += 1

    print(ans)

 

최대 100개 이하의 요소를 최대 101번까지 sort 하는 것은 1초 안에 가능하다. 왜 최대 101번 sort를 해야 하냐면 각 과목별 최소 마일리지를 한번 더 sort한 이후 작은 순부터 처리해야 하기 때문이다.