[구름톤 챌린지] Day15 : 과일 구매

입력 및 출력

소스 코드

n, k = map(int, input().split())
fruits = [list(map(int, input().split())) for _ in range(n)]
onepiece = []
for num, cost in fruits:
	pc = cost // num
	onepiece.append([pc, num])
onepiece.sort(reverse = True)
ans = 0
i = 0
while k > 0 and i < len(onepiece):
	if k >= onepiece[i][1]:
		ans += onepiece[i][0] * onepiece[i][1]
		k -= onepiece[i][1]
		i += 1
	else:
		ans += k * onepiece[i][0]
		onepiece[i][1] -= k
		k = 0
print(ans)

문제 풀이

K원을 가지고 가장 큰 포만감을 얻을 수 있도록 과일을 구매하는 문제이다.

이 문제가 쉬워진 이유는, 과일의 크기가 얼마든 간에, 1원으로 살 수 있도록 조각낼 수 있기 때문이다.

그래서 그냥 입력받은 과일에 대해 1조각으로 다 자른다음 그 조각이 몇개씩 있는지, 그 한 조각으로 얻을 수 있는 포만감은 얼마인지를 계산한다.

포만감이 높은 순서대로 정렬하고, 정렬한 리스트의 앞에서부터 K원을 쓸 때까지 과일을 1조각씩 사면 된다.

 

느낀 점

정말 그리디.. 그 자체였다.

문제를 언뜻봤을 때에는 배낭 문제인가 ? 했지만 전혀 아니었다.

한 주의 마지막 문제라 조금은 각오하고 문제를 풀기 시작했지만.. 생각보다 쉬웠던 것 같다.