[알고리즘 문제 풀기] Pareto(14410)

1. 문제 풀이 아이디어

• 정렬된 배열을 앞에서부터 누적하며 각 단계마다 그룹의 비율과 합의 비율 차이를 계산하고, 그 차이가 최대일 때의 값을 구해 문제를 해결할 수 있다.

2. 나의 정답 코드

using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
using (StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()))
{
    int n = int.Parse(sr.ReadLine());
    int[] num = new int[n];
    long sum = 0;
    string[] split = sr.ReadLine().Split();
    for (int i = 0; i < n; i++)
    {
        num[i] = int.Parse(split[i]);
        sum += num[i];
    }
    Array.Sort(num);
    Array.Reverse(num);
    long high = 0;
    double maxA = 0;
    double maxB = 0;
    for (int i = 0; i < n - 1; i++)
    {
        high += num[i];
        double a = 100.0 * (i + 1) / n;
        double b = 100.0 * high / sum;
        if (b - a > maxB - maxA)
        {
            maxA = a;
            maxB = b;
        }
    }
    sw.WriteLine($"{maxA}\n{maxB}");
}

3. 정리

• 입력으로 받은 정수 N과 N개의 정수를 배열에 저장한다.

• 전체 합계를 구하면서 배열을 오름차순 정렬한 뒤 Array.Reverse로 내림차순 정렬한다.

• 앞에서부터 누적합을 계산하면서, 인원 비율 a와 점수 비율 b를 계산한다.

• b - a 값이 최대가 되는 지점의 a와 b를 각각 maxA, maxB로 저장한다.

• 마지막에 해당 비율을 출력한다.