[ 구름톤 챌린지 ] 15일차 미션 - 과일 구매

구름톤 챌린지 3주차의 마지막 문제입니다. 챌린지를 통해 문제 풀이 실력을 향상시킬 수 있으며, 블로그에 학습 일기도 작성하면 추가 보상도 주어지니 관심 있으시면 참여해보시는 것을 추천드립니다.

https://level.goorm.io/l/challenge/goormthon-challenge

구름LEVEL

 

문제

입력과 출력

풀이 과정

과일을 조각내 구매할 수 있다는 것이 중요한 포인트이다. 

과일을 통으로 구매한다면 다르게 생각해야 했지만, 과일을 조각내서 일부만 구매할 수 있다면 일단 먼저 모든 과일을 조각내 놓고 포만감을 높게 채울 수 있는 조각을 먼저 가져가는 방법을 사용하면 된다.

조각의 가격은 모두 1이기 때문에, k 원을 만족할 때 까지 포만감을 높게 채울 수 있는 조각을 선택하는 행위를 반복하면 최대 포만감 합을 구할 수 있다.

 

다음은 예시 1번 입력에 제시된 과일 정보들을 모두 조각낸 상태이다. 같은 포만감을 가지는 조각들이 존재할 수 있으니 필자는 딕셔너리를 이용하여 중복된 포만감을 가지는 과일 조각들의 개수를 저장했다.

높은 포만감을 가지는 조각 순서대로 정렬해주면, 7포만감 1조각 / 5포만감 8조각 / 4포만감 5조각 / 3포만감 10조각 순서대로 저장된다. 과일의 개수는 1000개 까지로 제한되어 있기 때문에, 나올 수 있는 포만감의 종류는 1000종류여서 딕셔너리에 저장해도 무방하다.

 

과일 조각을 선택하는 과정을 조금 쉽게 만들기 위해, 누적 합을 이용하여 몇 원까지 사용하여 해당 과일 조각을 구매할 수 있는 지에 대한 정보를 저장했다. 이렇게 정보를 변환하면 다음과 같아진다.

7포만감 1조각 -> 7포만감 1원 ( 7포만감 조각을 1원까지 살 수 있음. )

5포만감 8조각 -> 5포만감 9원 ( 앞의 조각을 다 구매하고, 5포만감 조각을 9원까지 살 수 있음. )

4포만감 5조각 -> 4포만감 14원 ( 앞의 조각을 다 구매하고, 4포만감 조각을 14원까지 살 수 있음. )

3포만감 10조각 -> 3포만감 24원 ( 앞의 조각을 다 구매하고, 3포만감 조각을 24원까지 살 수 있음. ) 

 

이렇게 저장한 정보를 활용하여, k 원을 만족할 때까지 과일을 선택하는 반복문을 구현하면 최대 포만감 합을 구할 수 있다. 예시 1번의 k는 13이므로 4포만감 조각을 13원을 만족할 때까지 구매하므로, 7포만감 1조각 / 5포만감 8조각 / 4포만감 4조각 을 구매하게 된다. 

 

import sys
input = sys.stdin.readline

n, k = map(int, input().rstrip().split())

fruits = {}
for _ in range(n):
	p, c = map(int, input().rstrip().split())
	if fruits.get(c//p): fruits[c//p] += p
	else: fruits[c//p] = p

arr = list(fruits.items())
arr.sort(key=lambda x:-x[0])

order = []
sums = 0
for price, nums in arr:
	order.append([price, sums + nums])
	sums += nums

result = 0
pre_nums = 0
for price, nums in order:
	if nums < k:
		result += price * (nums - pre_nums)
		pre_nums = nums
	else:
		result += price * (k - pre_nums)
		break

print(result)