[BOJ 18319] Berry Picking

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

18319번: Berry Picking

 

- 문제 요약

 

베시와 그녀의 여동생 엘시는 농부 존의 베리밭에서 딸기를 따고 있습니다.

농부 John의 경작지에는 정확히 N개의 berry 나무가 있습니다
나무 i는 정확히 Bi 열매를 포함하고 있습니다
Bessie는 정확히 K 바구니를 가지고 있습니다
각각의 바구니는 베시가 원하는 만큼 한 나무의 열매를 담을 수 있지만, 맛이 서로 충돌하기 때문에 두 개의 다른 나무의 열매는 담을 수 없습니다. (바구니는 비어 있을 수 있습니다.)
Bessie는 그녀가 수집하는 베리의 수를 최대화하기를 원합니다.

하지만, 농부 존은 베시가 그녀의 여동생과 나눠 먹기를 원하기 때문에 베시는 엘시에게 가장 많은 수의 베리가 있는 K/2 바구니를 주어야 할 것입니다.

이것은 엘시가 심지어 베시보다 더 많은 열매를 맺게 될 수도 있다는 것을 의미하는데, 이것은 매우 불공평하지만, 불행히도 형제 역학이 항상 공평하지는 않습니다.
베시가 수집할 수 있는 최대 베리 수를 파악할 수 있도록 도와주세요.

 

 

- 알고리즘 정리

 

나무가 N개 있고, i번째 나무에는 Bi개의 열매가 달려있다고 했습니다.

최적의 경우에는 Bessie가 가지고 있는 모든 K-1개의 양동이에 베리가 하나씩 들어있어야 합니다. 

양동이를 하나씩 소비해 가면서 열매를 수확할 때, K개의 양동이를 다 쓰거나 모든 트리에 남아있는 딸기의 개수보다 적어질 때까지 반복문을 돌리면서 크기가 j인 양동이를 채워야 합니다.

이는 큰 값에서 작은 값으로 시행해야 합니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 100001
int n,k,arr[MAX],mod;

bool cmp(int a,int b){
	return (a%mod)>(b%mod);
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>k;
	int mx=0,result=0; 
	for(int i=0;i<n;i++){
		cin>>arr[i];
		mx=max(mx,arr[i]);
	} 
	for(int j=1;j<=mx;j++){
		int full=0;
		for(int i=0;i<n;i++){
			full+=arr[i]/j;
		}
		if(full<k/2){
			break;
		}
		if(full>=k){
			result=max(result,j*(k/2));
			continue;
		}
		mod=j;
		sort(arr,arr+n,cmp);
		int cur=j*(full-k/2);
		for(int i=0;i<n&&i+full<k;i++){
			cur+=arr[i]%j;
		}
		result=max(result,cur);
	}
	cout<<result<<'\n';
}

코드 제출 결과