[더블릿 - 4] 대표 자연수/natural

프로그램 명: natural

제한시간: 1 초

정보초등학교의 연아는 여러 개의 자연수가 주어졌을 때, 이를 대표할 수 있는 대표 자연수에 대하여 연구하였다. 그 결과 어떤 자연수가 다음과 같은 성질을 가지면 대표 자연수로 적당할 것이라고 판단하였다.

“대표 자연수는 주어진 모든 자연수들에 대하여 그 차이를 계산하여 그 차이들 전체의 합을 최소로 하는 자연수이다.”

예를 들어 주어진 자연수들이 [4, 3, 2,2, 9, 10]이라 하자. 이 때 대표 자연수는 3 혹은 4가 된다.

왜냐하면

• (4와 3의 차이) + (3과 3의 차이) + (2와 3의 차이) + (2와 3의 차이) + (9와 3의 차이) + (10과 3의 차이) = 1+0+1+1+6+7 = 16이고,
• (4와 4의 차이) + (3과 4의 차이) + (2와 4의 차이) + (2와 4의 차이) + (9와 4의 차이) + (10과 4의 차이) = 0+1+2+2+5+6 = 16으로 같으며,

이 두 경우가 차이들의 합을 최소로 하기 때문이다.

비교를 위하여 평균값인 5의 경우를 생각하여 보면, (4와 5의 차이) + (3과 5의 차이) + (2와 5의 차이) + (2와 5의 차이) + (9와 5의 차이) + (10과 5의 차이) = 1+2+3+3+4+5 = 18로 위의 두 경우보다 차이들의 합이 더 커짐을 볼 수 있다.

연아를 도와서 위의 성질을 만족하는 대표 자연수를 구하는 프로그램을 작성하시오.

입력

• 첫째 줄에는 자연수의 개수 N이 입력된다. N은 1 이상 20,000 이하이다.
• 둘째 줄에는 N개의 자연수가 빈칸을 사이에 두고 입력되며, 이 수들은 모두 1 이상 10,000 이하이다.

출력

첫째 줄에 대표 자연수를 출력한다.

대표 자연수가 두 개 이상일 경우 그 중 제일 작은 것을 출력한다.

입출력 예

입력

6
4 3 2 2 9 10

출력

3

출처 : 2009 KOI 전국본선 초등부 문제 1번
채점데이터: 대회데이터 + tncks0121(박수찬)

상당히 쉬운 문제다.
N개의 자연수가 입력 되었을 때,
이 때의 대표 자연수를 X라 하면

함수 f의 값이 최소 일 때의
X값을 구하는 문제이다.

절대값의 합으로 표현되는 위와같은 함수는
고등학교 때 나오는 문제로

그래프에 형태는
N이 짝수, 홀수에 따라 다르며
다음과 같다.

 
개략적인 그림으로 이해하길 바라며
이런 절대값의 합으로 표현되는 함수는
N이 홀수 개라면
가운데 수에서 유일한 최소값을 가지며
N이 짝수 개라면
가운데의 두 수 사이에서 최소값을 가진다.

따라서, 이 문제는
N개의 수를 입력받아
이를 정렬하여
가운데 수를 출력하는 프로그램으로 바꿔생각 할 수 있다. 

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

vector<int> a(20000);

int main()

{

    int n=0;

    cin>>n;

    for (int i=0;i<n;++i)

        cin>>a[i];

    sort(a.begin(),a.begin()+n);

    cout << a[(n-1)>>1];

    return 0;

}