https://www.acmicpc.net/problem/2109
시간 2초, 메모리 128MB
input :
- n(0 <= n <= 10000)
- p, d(1 <= p, d <= 10000)
output :
- 첫째 줄에 최대로 벌 수 있는 돈을 출력한다.
조건 :
- 예를 들어 네 대학에서 제시한 p값이 각각 50, 10, 20, 30이고, d값이 차례로 2, 1, 2, 1 이라고 하자. 이럴 때에는 첫째 날에 4번 대학에서 강연을 하고, 둘째 날에 1번 대학에서 강연을 하면 80만큼의 돈을 벌 수 있다.
- p의 값이 지불할 돈, d 날 안에 와서 강연 해야 됨.
이전에 풀던 그리디와 비슷한 문제로 가장 p가 센 것 부터 계속 계획된 날짜 안에 넣어줘야 한다.
3
1 1
10 2
10 2
와 같은 케이스에서 가장 많이 벌려면 20을 벌 수 있기 때문에 날짜 보단 지불되는 돈을 먼저 신경써야 한다.
그리고 기한이 많이 남아도 돈을 더 벌 수 있으면 이것을 먼저 하기 때문에 while문을 이용해 이 강연을 언제 할지 계획을 세우도록 한다.
import sys
ans = [0] * 10001
n = int(sys.stdin.readline())
data = []
for i in range(n):
p, d = map(int, sys.stdin.readline().split())
data.append((p, d))
data.sort(key= lambda x:-x[0])
for p, d in data:
while ans[d] != 0:
d -= 1
if d != 0:
ans[d] = p
print(sum(ans))최대 기한이 10000일 이니까 배열 길이를 10001로 만들어 모든 경우를 저장하도록 한다. 페이가 가장 큰 것을 확인하기 위해 내림차순 정렬을 하고 수행한다.
