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()
ps/problems/boj/34826.txt · 마지막으로 수정됨: 2026/01/29 13:40 저자 teferi

토론