사용자 도구

사이트 도구


ps:problems:boj:34826

Yonsei TOTO 2

ps
링크acmicpc.net/…
출처BOJ
문제 번호34826
문제명Yonsei TOTO 2
레벨골드 5
분류

그리디

시간복잡도O(nlogn)
인풋사이즈n<=100,000
사용한 언어Python 3.13
제출기록49392KB / 124ms
최고기록124ms
해결날짜2026/01/29

풀이

  • 이전 문제였던 Yonsei TOTO 이 2016년도 대회에서 나온지 거의 10년이 지난 2025년 대회에서 후속 문제가 나왔다. 그동안 학교의 수강신청 방식이 실제로 이렇게 바뀌었는지는 모르겠다
  • 전체 만족도는 과목별 만족도의 합이다. 기댓값의 선형성에 따라서, 전체 만족도의 기댓값은 과목별 만족도의 기댓값의 합이다.
  • i번째 과목에 마일리지를 1만큼 추가 베팅하면, 만족도는 Bi/Ai 만큼 올라간다.
  • 따라서 Bi/Ai가 큰 과목순으로 마일리지를 최대한씩 투자하면 된다. (min(M,Ai) 만큼 투자하면 된다)
  • 시간복잡도는 정렬하는데에 걸리는 O(nlogn)에 바운드된다

코드

"""Solution code for "BOJ 34826. Yonsei TOTO 2".

- Problem link: https://www.acmicpc.net/problem/34826
- Solution link: http://www.teferi.net/ps/problems/boj/34826

Tags: [greedy]
"""

import sys


def main():
    N, M, S = [int(x) for x in sys.stdin.readline().split()]
    A = [int(x) for x in sys.stdin.readline().split()]
    B = [int(x) for x in sys.stdin.readline().split()]

    sorted_inds = sorted(range(N), key=lambda i: B[i] / A[i], reverse=True)

    answers = [0] * N
    for i in sorted_inds:
        answers[i] = betting_amount = min(A[i], M, S)
        S -= betting_amount
        if S == 0:
            break

    print(*answers)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
U D Q S Z
 
ps/problems/boj/34826.txt · 마지막으로 수정됨: 2026/01/29 13:40 저자 teferi