[BOJ-2548]대표 자연수

대표 자연수란?

여러개 자연수가 주어졌을 때, 

여러개 자연수 중에 대표할 자연수를 뜻한다. 

대표 자연수는 여러개 자연수와 차이를 절대값 씌워 모두 합했을 때, 이 합한 값이 최소가 되는 자연수를 말한다.

이 합한 값이 최소가 되는 자연수가 여러개 인 경우에는 가장 작은 값을 택한다. 

[입력]

n 

a1

a2

..

an-1

an

n개의 자연수가 입력으로 주어지며, n~[1, 20,000]

다음 2..n+1줄에는 여러개 자연수가 주어짐. ai~[1, 10,000]

[출력]

대표 자연수를 출력한다.

[접근방법]

처음에 시간초과 한번 받고 시작하겠구나 생각했었다. 

방법은 이렇다. 

모든 수를 입력받은 후, 정렬, 선형적으로 이중 반복문 (for) 를 이용해서

 모든 자연수의 대표 자연수가 될 수 있는 값(모든 자연수와 차이합) 을 구해서 넣는다. 

1) 가장 큰 수 부터 시작해서,  for  an to a1 

2) 대표 자연수가 될 수 있는 값을 비교하여 최소가 되는 값이 발생하면 (  if min > res[ai] )

3) 최소값을 갱신시키고, 대표 자연수 값도 갱신한다. ( min = res[ai] , ans = ai ) 

2) 그런데 최소값이 여러개 일 경우 낮은 값을 대표 자연수 값으로 하기 때문에 ( if min >= res[ai] ) 를 추가한다.

여기서 입력이 1부터 10,000 까지가 수 ai 의 범위이므로 정렬을 사용하지 않고 배열의 인덱스를 사용해서 풀이하였다. 

그러면 정렬할 필요가 없어지고, 만약 수가 20,000 이면 -> 10,000개까지 줄일 수 있으므로 그렇게 했다. 

그래도 시간초과가 발생할 것이라고 생각했는데?

아니였다. 왜 그런지  for 1 to 10000 ( for 1 to 10000) 이면 적어도 1억번인데

여튼 이렇게 풀었다.

#include<cstdio>
#include<vector>
#include<algorithm>
#define din1(a) scanf("%d", &a)
#define pb(a) push_back(a)
using namespace std;
const int MMAX = 11111;
const int INF = 987654321;
int input[MMAX];
 
int res[MMAX];
int ab(int a) {
    return (a > 0)?a:-a;
}
int main() {
    int n; din1(n);
    for (int i = 0; i < n; i++) {
        int temp;
        din1(temp);
        input[temp]++;
    }
 
    for (int i = 1; i <= 10000; i++) {
        if (input[i] == 0) {
            res[i] = INF;
            continue;
        }
        int pivot = i;
        int result = 0;
        for (int idx = 1; idx <= 10000; idx++) {
            if (pivot == idx) continue;
            result += input[idx] * ab(pivot-idx);
        }
        res[pivot] = result;
    }
 
    int mi = INF - 1;
    int ans = -1;
    for (int i = 10000; i >= 1; i--) {
        if (mi >= res[i]) {
            mi = res[i];
            ans = i;
        }
    }
    printf("%d", ans);
 
    
    return 0;
}