[구름톤 챌린지 #15] 과일 구매

문제15. 과일 구매

구름LEVEL

---

---

문제 해결 방법

오늘 문제에서 가장 주의 깊게 보아야할 조건은 바로 "과일을 조각 단위로 구매하는 것이 가능하다"는 조건이다. 이 조건이 없었다면, 과일들의 가격이 다르고, 과일마다 포만감이 다르기 때문에 그리디 알고리즘을 적용할 수 없다. 그럴때는 완전탐색이나 DP 등의 알고리즘을 적용해야 풀 수 있는 문제였을 것이다.

 

하지만 오늘 문제에는 "과일을 조각 단위로 구매하는 것이 가능하다"는 조건이 있다. 과일을 조각 단위로 구매한다면 가격이 p인 과일 하나를, 가격이 1인 p개의 과일 조각으로 나눌 수 있다. 그리고 이때의 각 과일 조각의 포만감은 c/p가 된다. 이제는 가격이 모두 1로 동일한 과일 조각들이 있을 때, 과일 조각들로 얻을 수 있는 최대 포만감을 구하는 문제로 변환할 수 있다. 이제는 가장 포만감이 높은 과일 조각을 먼저 고르는 그리디 알고리즘을 적용할 수 있는 문제가 되었다.

 

위의 아이디어를 조금만 더 발전시켜보면, 모든 과일을 조각내는 대신, 가격 당 포만감이 가장 높은 과일부터 통째로 먹되 남은 돈으로 해당 과일을 통째로 먹을 수 없는 상황이 되면, 남은 돈으로 그 과일을 몇 조각 사면 된다.

 

위 내용을 코드로 구현하면 아래와 같다.

import sys

n, k = map(int, sys.stdin.readline().split())

pc_arr = []

for i in range(n):
    p, c = map(int, sys.stdin.readline().split())
    c_divided_by_p = c // p
    pc_arr.append([c_divided_by_p, p, c])

#c_divided_by_p가 낮은 순서대로 정렬 (뒤에서부터 pop할거임)
pc_arr.sort()

result = 0
while True:
    #돈이 남아도 과일이 없으면 못삼
    if not pc_arr:
        break

    #가격 당 포만감이 가장 높은 것부터 먹어야함
    fruit = pc_arr.pop()

    #현재 과일을 다 먹을 수 없다면 현재 과일을 조각으로 먹을 수 있음
    if fruit[1] > k:
        result += k * fruit[0]
        break
        
    k -= fruit[1]
    result += fruit[2]

print(result)