Problem

문제 설명

가격당 포만감이 가장 높은 과일 종류 순으로 과일 조각을 구매했을 때, 최대 포만감을 계산한다.

1. 구매할 과일 조각의 개수는 예산 한도 내에서 항상 최대 개수로 선택한다.
2. 가격 p일 때 과일을 p 조각낼 수 있으므로, 가격과 과일 조각의 최대 개수가 동일하다.

필요한 알고리즘

그리디

Submitted Code

Python

 1 N, K = map(int, input().split())
 2 fruits = [0] * N
 3 for i in range(N):
 4     P, C = map(int, input().split())
 5     fruits[i] = (C // P, P)
 6 fruits.sort(reverse=True)
 7
 8 fullness = 0
 9 for c, p in fruits:	
10     cnt = min(K, p)
11     fullness += c * cnt
12     K -= cnt	
13     if K == 0:
14         break
15
16 print(fullness)

Line 1

과일의 개수 N과 예산 K을 입력받는다.

Line 2-5

fruits에 (가격당 포만감 C // P, 가격 P)을 저장한다.

Line 6

가격당 포만감을 기준으로 fruits를 내림차순으로 정렬한다.

Line 8

포만감 총합을 기록할 fullness를 0으로 초기화한다.

Line 9-14

가격당 포만감이 큰 과일 순서대로 구매한다.

Line 10

현재 남은 예산 K과 과일 조각의 최대 개수 p 중 작은 개수를 구매가능한 개수 cnt에 저장한다.

• 현재 남은 예산 >= 과일 조각의 최대 개수일 때, 과일 조각의 최대 개수만큼 구매할 수 있다.
• 현재 남은 예산 < 과일 조각의 최대 개수일 때, 남은 예산만큼 구매할 수 있다.

Line 11

가격당 포만감 * 구매가능한 개수를 포만감 총합 fullness에 더한다.

Line 12

구매가능한 개수만큼 예산을 사용했으므로, 예산의 남은 양을 업데이트한다.

Line 13-14

현재 남은 예산 K가 0이면, for문을 종료하여 과일 구매를 중단한다.

Line 16

포만감 총합 fullness를 출력한다.

C++

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	int N;
	long K;
	cin >> N >> K;
	
	pair<long, long> fruits[1000];
	for (int i = 0; i < N; i++) {
		long price, fullness;
		cin >> price >> fullness;
		fruits[i].first = fullness / price;
		fruits[i].second = price;
	}
	sort(fruits, fruits + N);
	
	long long total_fullness = 0;
	for (int i = N - 1; i >= 0; i--){
		long cnt = min(K, fruits[i].second);
		total_fullness += fruits[i].first * cnt;
		K -= cnt;
		if (K == 0) {
			break;
		}
	}
	
	cout << total_fullness;
	return 0;
}