알고리즘/BOJ
[Python] 백준 1781: 컵라면
PIAI
2021. 9. 14. 18:07
1781번: 컵라면
상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라
www.acmicpc.net
1. 컵라면수가 많은순으로 정렬한다.
2. find 함수로 날짜에 맞춰 채워나간다.
3. 날짜에 채웠으면 그 날짜에는 채우지 못하므로 배열의 값을 한개 내려준다.
4. find 함수로 계속해서 채울수있는 날짜를 채워나간다.
n = int(input())
ans = 0
pay = []
deadline = [i for i in range(200001)]
def find(x):
if x == 0:
return 0
if x == deadline[x]:
deadline[x] -= 1
return x
else:
deadline[x] = find(deadline[x])
return deadline[x]
for _ in range(n):
pay.append(list(map(int, input().split())))
pay.sort(key=lambda x: -x[1])
for x, y in pay:
if find(x) > 0:
ans += y
print(ans)