[C++] 백준 2548번:대표 자연수

문제링크

2548번: 대표 자연수

문제

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

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

예를 들어 주어진 자연수들이 [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 이하이다.

출력

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

 

풀이

완전탐색으로 해결할 수 있다.

입력 받은 모드 수를 돌면서 차이의 합이 가장 작은 수를 찾는다.

 

코드

#include <iostream>
#include <vector>
using namespace std;
 
int n;
 
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
    vector<int> v(n);
 
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
 
    int result = 2000000000;
    int ans = n - 1;
    for (int i = 0; i < n; i++) {
        int tmp = 0;
 
        // 차의 합
        for (int j = 0; j < n; j++) {
            tmp = tmp + abs(v[i] - v[j]);
        }
 
        // 원래 값보다 작다면 index와 합 갱신
        if (tmp < result) {
            ans = i;
            result = tmp;
        }
 
        // 원래 값과 같다면 더 작은 값으로 갱신
        if (tmp == result) {
            if (v[i] < v[ans]) {
                ans = i;
            }
        }
    }
 
    cout << v[ans];
}

++

문제에서 설명하는 대표 자연수가 곧 중앙값의 설명이다. (이걸 어떻게 한번에 아는거지?!)

통계집단의 변량을 크기의 순서로 늘어 놓았을 때, 중앙에 위치하는 값 - 네이버 지식백과

 

문제가 중앙값을 구하는 것이라는 것을 알면 코드가 더 쉬워지고 간단해진다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int n;
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
    vector<int> v(n);
     
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
 
    sort(v.begin(), v.end());
 
    cout << v[(n - 1) / 2];
}