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

1. 문제이해

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

2548번: 대표 자연수

 

모든 자연수들에 대해 차이를 계산하여 그 차이들 전체의 합을 최소로 하는 자연수를 대표 자연수라고 한다.

N개의 자연수가 주어질 때, 그 중 대표 자연수를 출력하는 것이 목표이다.

(단, 대표 자연수가 2개 이상일 경우, 가장 작은 숫자를 대표 자연수로 출력한다.)

 

 

 

2. 문제풀이

 

문제의 의도만 잘 파악하면 어렵지 않은 문제이다.

N개의 자연수 중 전체 차이의 합을 최소로 하는 값을 찾는 것이 목표이다.

언뜻 보면 평균값과 가장 가까운 숫자를 찾는게 아닌가 싶지만, 실은 해당 문제는 중앙값을 찾는 문제이다.

아래 예제를 통해 자세히 알아보자.

 

---

 

<예제 입력 1>

N = 6

 4  3  2  2  9  10

 

위와 같이 주어진 6개의 숫자들을 우선 오름차순으로 정렬해보면, 다음과 같다.

2  2  3  4  9  10

해당 수들의 평균값은 (2 + 2+ 3 + 4 + 9 + 10) / 6 = 5 로, 가장 가까운 수는 4이다.

하지만, 4는 대표 자연수가 아니다.

모든 자연수들에 대해 차이의 합을 계산해보면 3과 4가 대표 자연수 후보로 나오게 되고,

더 작은 값을 대표 자연수로 채택하기 때문에 3이 대표 자연수가 된다.

즉, 평균값에 가장 가까운 값이라고 해서 모두 대표 자연수가 된다는 것은 아니며,

중앙값을 채택하는 것이 곧 대표 자연수를 채택하는 것이 된다.

(단, N이 짝수일 경우 중앙값이 2개 나오게 되는데, 이 중 작은 값을 대표 자연수로 채택한다.)

 

 

<예제 입력 N>

N = 6

 4  3  2  2  9  10

 

위와 같이 극단적으로 큰 자연수 하나가 포함되어있는 경우를 보자.

위와 같이 주어진 6개의 숫자들을 우선 오름차순으로 정렬해보면, 다음과 같다.

2  2  3  4  9  100

해당 수들의 평균값은 (2 + 2+ 3 + 4 + 9 + 100) / 6 = 20 으로, 가장 가까운 수는 9이다.

하지만, 9는 대표 자연수가 아니다.

9를 이용한 모든 자연수의 차이의 합을 계산해보면, (9 - 2) + (9 - 2) + (9 - 3) + (9 - 9) + (100 - 9) =  111 이다.

 

그러면, 중앙값을 한번 보자.

자연수의 개수가 짝수개이므로, 3과 4 가 중앙값이 되며, 더 작은 값을 대표 자연수로 채택하므로,

3을 이용한 모든 자연수의 차이의 합을 계산해보면, (3 - 2) + (3 - 2) + (3 - 3) + (9 - 3) + (100 - 3) =  105 이다.

 

---

 

중앙값은 평균값과 다르게 관측값들의 변화에 민감하지 않다.

즉, 극단적으로 큰 값이나 작은 값에 영향을 받지 않는다.

따라서 평균값이나 해당 값에 가까운 값보다 중앙값을 채택하는 것이,

해당 자연수를 대표하는 올바른 대표 자연수라고 말할 수 있다.

즉, 위 예제들을 통해 볼 수 있듯 중앙값을 채택하는 것이 곧 대표 자연수를 구하는 것이다.

 

 

 

3. 소스코드

#include <iostream>
#include <algorithm>
using namespace std;

int num[20000];

int main() {
	int N;
	int rep;

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> num[i];
	}

	// 입력받은 숫자들을 정렬
	sort(num, num + N);

	// 1. N의 개수가 짝수인 경우
	//    중앙값이 2개이므로 더 작은 값 채택
	if (N % 2 == 0) {
		cout << num[N / 2 - 1];
	}
	// 2. N의 개수가 홀수인 경우
	//    중앙값이 1개이므로 바로 채택
	else {
		cout << num[N / 2];
	}

	return 0;
}

2. 문제풀이에서 알 수 있듯, 입력받은 자연수들 중 중앙값을 출력해주면 된다.

먼저 자연수의 개수 N과 자연수들을 입력받는다.

입력받은 숫자들을 오름차순으로 정렬한 뒤,

N의 개수가 짝수인지, 홀수인지 판별 후 알맞은 중앙값을 출력한다.

 

만약, N이 짝수인 경우, 중앙값 2개중 더 작은 값이 대표 자연수이므로,

num[N / 2 - 1] 을 해주어 더 작은 값을 출력한다.

(ex) 2  2  3  4  9  10 의 대표 자연수 = num [6 / 2 - 1] = num[2] = 3)

 

만약, N이 홀수인 경우, 중앙값이 대표 자연수이므로,

num[N / 2] 을 출력한다.

(ex) 2  2  3  4  9  10 12 의 대표 자연수 = num [7 / 2] = num[3] = 4)

 

 

---

백준의 난이도는 알다가도 모르겠다..

실버인데 골드 정도로 어려운 문제도 있고, 브론즈 정도로 쉬운문제도 있고..😭

 

문제에 대한 질문이나 지적은 언제나 감사하게 받고 있습니다.😊