[2551번] 두 대표 자연수

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 수학

이 문제는 [2548번] 두 대표 자연수 :: http://www.crocus.co.kr/961 문제를 먼저 풀어 볼 것을 추천한다.

위의 링크에서 첫번째 풀이 방법에 대해 이야기를 해 두었기에 위의 링크를 확인해볼 것을 추천한다.

이 글에서는 두번째 풀이 방법에 대해 알아보고자 한다.

(a1-k)^2 + (a2-k)^2 + ... + (an-k)^2을 풀어보면

처럼 구성 되고 이 식을 묶으면

이 된다.

따라서 이 식의 최솟값이 되는 k를 찾아내면 되기에 결국 k를 1~10000까지 조사하며 찾아내주면 된다.

이때 조금 더 수학적인 면으로 보고자 한다면 다음과 같은 기법을 이용한다.

1. 차이의 절댓값의 합을 최소화 시키는 값은, 원래 수들의 median 이고

2. 차이의 제곱의 합을 최소화 시키는 값은, 원래 수들의 mean 임을 이용한다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67

#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <limits.h>   using namespace std;   long long presum[5000002]; long long powsum[5000002]; long long arr[5000002];   const long long MIN = LONG_MAX;   int main() {     int n;     scanf("%d", &n);       for (int i = 1; i <= n; i++)         scanf("%lld", &arr[i]);       sort(arr + 1, arr + n + 1);       // 구간 합, 구간 제곱 합     for (int i = 1; i <= n; i++)     {         presum[i] = presum[i - 1] + arr[i]; // 합         powsum[i] = powsum[i - 1] + arr[i] * arr[i]; // 제곱     }       long long ans = MIN;     int pos = -1;     for (int k = 1; k <= n; k++)     {         long long sum = (long long)(k - 1)*arr[k] - presum[k - 1] + presum[n] - presum[k] - (long long)(n - k)*arr[k];           if (ans > sum)         {             ans = sum;             pos = k;         }     }     cout << arr[pos] << " ";       ans = MIN;     pos = -1;       int start = arr[1];     int end = arr[n];     for (int k = 1; k <= 10000; k++)     {         long long sum = powsum[n] - (long long)2 * k * presum[n] + (long long)n * k * k;           if (ans > sum)         {             ans = sum;             pos = k;         }     }       cout << pos;     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus