[2548번] 대표 자연수

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 수학

2. Prefix Sum :: http://www.crocus.co.kr/843

이 문제는 수학적 지식을 요구하는 문제이다.

어떤 수를 골랐을 때 입력받은 모든 수와 그 수의 차이중 최소가 되는 값을 구해야 하는 문제이다.

그럼 결국 다음과 같은 식이 될 것이다.

어떤 수를 k라 하였을 때 |a1- k| + |a2-k| + ... + |k-k| + ... + |an - k|인 값 중 최소 k를 구해야 한다.

그럼 어떤 수 k를 기준으로 k보다 작은 수는 -k를 했을 때 음수가 되고, k보다 큰 수는 -k를 했을 때 양수가 된다.

이제 절댓값을 풀어보면 bk - a1 - a2 - ... + k-k + an-3 + an-2 + an-1 + an - ck가 됨을 알 수 있다.

즉, bk - (a1 + a2 + ... )+ k-k + (an-3 + an-2 + an-1 + an) - ck

따라서 이 방법을 이용하여 왼쪽 오른쪽을 나누어 더해주는 방식을 고려해본다.

우선 입력을 받고 그 값을 정렬해보자.

6
4 3 2 2 9 10

에서

6
2 2 3 4 9 10

으로 변하게 된다.

이를 이용하여 Prefix Sum을 이용하여 구간 합을 모두 구해주고 위의 모양대로 for문을 돌며 결과값을 찾아 낼 수 있다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
 
using namespace std;
 
int main()
{
    int n;
    int prefix[20002] = { 0 };
    scanf("%d", &n);
 
    vector<int> vc;
 
    for (int i = 0; i < n; i++)
    {
        int val;
        scanf("%d", &val);
 
        vc.push_back(val);
 
    }
 
    sort(vc.begin(), vc.end());
 
    for (int i = 0; i < n; i++)
    {
        if (i == 0)
            prefix[0] = vc[0];
        else
            prefix[i] = prefix[i - 1] + vc[i];
    }
 
    int ans = 2e9;
    int pos = -1;
 
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum += abs(vc[i] - vc[0]);
 
    if (ans > sum)
    {
        ans = sum;
        pos = 0;
    }
 
    for (int k = 1; k < n; k++)
    {
        int sum = 0;
        sum = k * vc[k] - prefix[k-1] + (prefix[n - 1] - prefix[k]) - (n-1 - k)*vc[k];
 
        if (ans > sum)
        {
            ans = sum;
            pos = k;
        }
    }
    
    printf("%d", vc[pos]);
 
    return 0;
} 
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>