본문 바로가기

Algorithm

1246 온라인 판매 / 그리디

 

정답

  • i번째 고객은 pi에 해당하는 수의 이하의 가격만 살 수 있음
N = 5 (달걀 수)
고객들이 제시한 가격 P = [2, 8, 10, 7]

 

  • A=7로 정하면 7 이상 지불 가능한 고객은: 7, 8, 10 → 총 3명
  • 수익 = 7원 × 3개 = 21원
  • 하지만 총 달걀의 수를 초과해서 구매할 수 없기 때문에 min함수를 사용하여 고객과 달걀의 수 중에서 최소값을 고른다
n, m = map(int, input().split()) # 달걀의 개수, 손님의 수
consumer = [] # 각 손님별로 구매할 수 있는 가격의 최대값
for _ in range(m):
    price = int(input())
    consumer.append(price)

consumer.sort()
idx = 0
ans_price = 0
ans_egg_price = 0
for p in consumer:
    count = min(n, len(consumer[idx:]))
    idx = idx + 1
    max_price = count * p
    if ans_price < max_price:
        ans_price = max_price
        ans_egg_price = p

print(ans_egg_price, ans_price)

'Algorithm' 카테고리의 다른 글