백준 23742 (Player-based Team Distribution) c++

문제

23742번: Player-based Team Distribution

n개의 수가 주어지면 1개 이상의 팀을 나누고 팀의 점수는  팀원수의 합 * 팀원 구성원의 합 입니다.

모든 플레이어의 점수 합의 최댓치를 구하면 됩니다.

예를 들어 n이 4이고 주어진 숫자가 2, 3, -4, 1 이면 {2, 3, 1}, {-4} 로 팀을 나누면

3 * (2+3+4) + 1 * -4 = 14 가 됩니다. 

 

단순히 생각해보면 주어진 n개의 수중에서 양수는 모두 팀을 이루어지고 음수는 각각 구성원이 1이 팀으로 짜주면

최댓치가 나올것 같습니다.

 

하지만 반례가 존재합니다.

예를 들어 n이 4이고 주어진 숫자가 2, 3, -1, 1 이라면 

{2, 3, 1}, {-1} = 3 * (2 + 3 + 1) + 1 * -1 = 17

{2, 3, -1, 1} = 4 * (2 + 3 + -1 + 1) = 20

따라서 음수가 같은 팀이 되더라도 점수 합의 최댓치가 존재한다는 것을 알 수 있습니다.

 

1) i번째 구성원의 누적합 * 팀원수

2) 이전의 합 + 현재 플레이어의 점수

 

1과 2중에 더 큰 수를 sum에 계속해서 저장해주면서 끝까지 탐색해주면 됩니다.

for (int i = 1; i <= n; i++) {
	cin >> arr[i];
}
sort(arr+1, arr+n+1,cmp);

i가 1부터 n개의 숫자를 입력받습니다.

입력받은 arr배열을 내림차순으로 정렬합니다.

arr[1] ~ arr[n] 까지 탐색하면서 제일 큰 수 부터 sum에 넣으면서 판단해줘야 하기 때문입니다.

sum = arr[1];
for (int i = 1; i <= n; i++)
	prefix[i] = prefix[i - 1] + arr[i];

for (int i = 2; i <= n; i++) {
	sum = max(i*prefix[i], sum+arr[i]);
}
cout << sum;

먼저 n이 1이 들어올 수 있으므로 sum에다가 arr[1]의 값을 저장합니다.

perfix배열은 누적합입니다.

이제 i는 2부터 탐색하면서

1) i번째 구성원의 누적합 * 팀원수

2) 이전의 합 + 현재 플레이어의 점수

1과 2 중에 더 큰수를 sum에다가 저장합니다.

---

전체 코드입니다.

#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<time.h>
#include<cstring>
#include<cmath>
#include<cstring>
#include<limits>
#define inf INT_MAX
using namespace std;
using ll = long long;
using ull = unsigned long long;
ll arr[100001];
ll sum;
ll ans = 0;
ll n;
ll prefix[100001];
bool cmp(ll a, ll b);
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	sort(arr+1, arr+n+1,cmp);
	sum = arr[1];
	for (int i = 1; i <= n; i++)
		prefix[i] = prefix[i - 1] + arr[i];

	for (int i = 2; i <= n; i++) {
		sum = max(i*prefix[i], sum+arr[i]);
	}
	cout << sum;
	return 0;
}
bool cmp(ll a, ll b) {
	return a > b;
}