[구름톤 챌린지] 3주차 15일차 과일 구매

 

 

문제

---

과일을 사기 위해 마트를 간 플레이어는 큰 난관에 봉착했다. 왜냐하면 팔고 있는 과일이 너무 많아서, 어떤 과일을 사면 좋을지 결정하는 게 너무 어려웠기 때문이다. 현재 마트에서 팔고 있는 과일은 $N$종류가 한 개씩 있고, 각 과일의 가격은 $P_i$, 그리고 그 과일을 먹었을 때 플레이어가 얻을 수 있는 포만감은 $C_i$이다.

이 마트에서는 특이하게도 과일을 조각 단위로 구매하는 것이 가능하다. 가격이 $p$인 과일을 조각 단위로 구매하고자 할 경우, 플레이어는 이 과일을 $p$개의 조각으로 자른 뒤 그중 원하는 몇 개의 조각만을 구매할 수 있다. 이때 모든 조각의 가격은 $1$, 먹었을 때 얻을 수 있는 포만감은 $C_i/P_i$로 동일하다.

플레이어는 $K$만큼의 돈을 가지고 있다. 플레이어는 주어진 금액 이내에서 구매한 과일들의 포만감 합이 가장 크게 되도록 살 과일을 선택하려고 한다. 플레이어가 최적의 방법에 따라 과일을 구매했을 때, 구매한 과일들의 최대 포만감 합을 구해보자.

입력

---

첫째 줄에 마트에서 파는 과일의 개수 $N$과 플레이어가 가진 돈 $K$가 공백을 두고 주어진다.
다음 $N$개의 줄에는 각 과일의 가격 $P_i$와 그 과일을 먹었을 때 플레이어가 얻을 수 있는 포만감 $C_i$가 공백을 두고 주어진다.

 

 

• $1 \leq N \leq 1 \ 000$
• $1 \leq K \leq 10^9$
• $1 \leq P_i \leq 10^9$
• $1 \leq C_i \leq 10^9$
• $C_i$는 항상 $P_i$의 배수이다.
• 입력에서 주어지는 모든 수는 정수이다.

출력

---

플레이어가 구매한 과일들의 최대 포만감 합을 출력한다.

 

---

문제 접근 방식

---

분할 가능한 배낭문제로, 매우 유명한 그리디 문제이다.

 

가격 대비 가장 많은 포만감을 얻을 수 있는 순으로 정렬한 뒤 가격 대비 가장 많은 포만감을 얻을 수 있는 과일 먼저 사면 된다.

 

---

정답 코드

---

# 과일 구매
import sys
input = sys.stdin.readline

N, K = map(int, input().rstrip().split())
li = sorted((tuple(map(int, input().rstrip().split())) for _ in range(N)), key = lambda tpl: tpl[1]//tpl[0])
total_C = 0
while K and li:
    P, C = li.pop()
    if K < P:
        total_C += K*C//P
        K -= K
    else:
        total_C += C
        K -= P
print(total_C)

 

---

특별히 배운 점

---

분할가능하지 않은 배낭문제는 DP로 해결할 수 있다.