python 백준 28103 대회 상품 정하기

https://www.acmicpc.net/problem/28103

로직

• 사람을 한명씩 가진돈과 비교하여 계산할 경우 N이 너무 커서 시간초과가 발생
• 가격의 경우 10**6으로 반복문을 돌려도 문제가 발생하지 않는 범위
• 일단 모두 제일 싼 값으로 구매한 후 남은 돈으로 계산 시작 (X -= default*N)
• 위 방법으로 계산하기 위해 물건의 가격을 제일 값싼 물건과의 가격차이로 변경
• 가장 비싼물건부터 여유있는 돈의 수만큼 구매, 이 때 현재 남아있는 사람 수(N)와 비교하여 낮은 값으로 계산
  • 현재 가진돈이 물건 값 대비 매우 많을 경우 X//price 계산시 사람 수보다 많은 물건을 사게됨
• 가장 값싼 물건과의 가격차이로 list를 변경하여 prices[-1]은 0이 되어 X//price 시 zerodivision err가 발생하므로 M-1까지만 반복

N,M,X = map(int,input().split())
prices = list(map(int,input().split()))
default = prices[-1]
X -= default*N
for m in range(M):
    prices[m] -= default
ans = [0]*M

for m in range(M-1):
    price = prices[m]
    if price:
        value = min(X//price,N)
        ans[m] += value
        N -= value
        X -= value*price
ans[-1] = N
print(*ans)