[BOJ 13217 // C++] Honey

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 13217번 문제인 Honey이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/13217 

13217번: Honey

한번에 꿀을 M씩 가져오는 것이 최선의 수이므로, M씩 가져올 수 있는 횟수를 미리 구해두자. 또한, 이와 같이 시행했을 때 각 나무에 남는 꿀의 양을 구해두자.

 

한번에 꿀을 M씩 가져올 수 있는 횟수가 K 이상이면 한번에 꿀을 M씩 K번 가져오는 것으로 문제를 해결할 수 있다.

 

그렇지 않은 경우, 남은 꿀 중 한번에 가장 많이 가져올 수 있는 나무부터 순서대로 꿀을 가져오는 것으로 문제를 해결할 수 있다.

 

K가 충분히 클 경우 K번 모두를 굳이 움직일 필요는 없다는 점을 고려해 위의 내용을 구현하자.

 

문제의 답이 32비트 정수 자료형을 넘을 수 있으므로 이에 유의해 구현하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

ll N, M, K;
ll arr[200000];

ll fullcnt;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M >> K;
	for (int i = 0; i < N; i++) {
		ll& cur = arr[i];
		cin >> cur;

		fullcnt += cur / M; cur %= M;
	}

	sort(arr, arr + N);

	if (K <= fullcnt) cout << K * M;
	else {
		ll ans = fullcnt * M;
		K = min(N, (K - fullcnt));
		for (int i = 0; i < K; i++) ans += arr[N - 1 - i];

		cout << ans;
	}
}