[BOJ 14410 // C++] Pareto

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

 

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

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

14410번: Pareto

이 문제는 파레토 법칙(Pareto's Principle)을 소재로 한 문제이다. 이탈리아의 경제학자 Pareto가 제시한 법칙으로, 일반적으로 20%의 원인이 80%의 결과를 만들어낸다는 법칙이다. 80/20 법칙 등으로도 불린다.

 

문제에서 주어진 설명대로 N개의 계좌 중 k개의 "가장 많은 금액이 들어있는 계좌의 액수"의 합을 이용해 각 k값에서의 B-A의 값을 계산하고 이중 B-A가 최대일 때의 A와 B값을 출력하는 것으로 문제를 해결하자. 정렬과 누적합 변수를 이용하면 이를 O(NlgN)에 계산해낼 수 있다.

 

주어진 식의 분모에 있는 수들을 각각 양변에 곱해 계산한다면 실수오차 없이 A와 B의 값을 저장된 정수들만으로 정확히 표현할 수 있다.

 

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

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

int N;
ll arr[300000];
ll A, B;
ll psum = 0, total = 0;
ll ansval = -1000000000000000007LL;

bool comp(ll& x, ll& y) {
	return x > y;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int i = 0; i < N; i++) {
		ll& x = arr[i];
		cin >> x;
		total += x;
	}
	sort(arr, arr + N, comp);

	for (int i = 0; i < N; i++) {
		psum += arr[i];
		if (psum * N - (i + 1) * total > ansval) {
			ansval = psum * N - (i + 1) * total;
			A = i + 1, B = psum;
		}
	}

	cout << fixed;
	cout.precision(10);

	cout << (double)(100 * A) / N << '\n' << (double)(100 * B) / total;
}