문제
정보초등학교의 연아는 여러 개의 자연수가 주어졌을 때, 이를 대표할 수 있는 대표 자연수에 대하여 연구하였다. 그 결과 어떤 자연수가 다음과 같은 성질을 가지면 대표 자연수로 적당할 것이라고 판단하였다.
“대표 자연수는 주어진 모든 자연수들에 대하여 그 차이를 계산하여 그 차이들 전체의 합을 최소로 하는 자연수이다.”
예를 들어 주어진 자연수들이 [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 이하이다.
출력
첫째 줄에 대표 자연수를 출력한다. 대표 자연수가 두 개 이상일 경우 그 중 제일 작은 것을 출력한다.
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
|
#include<stdio.h>
#include<math.h>
#pragma warning(disable:4996)
#pragma warning(disable:6031)
int arr[20000];
int get_dif(int num, int size) {
int sum = 0;
for (int i = 0; i < size; i++)
sum += abs(arr[i] - num);
return sum;
}
int main()
{
int n, max = 0, min = 10001,temp, dif = 0x7fffffff, ans;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
if (arr[i] > max)max = arr[i];
if (arr[i] < min)min = arr[i];
}
for (int i = min; i <= max; i++) {
temp = get_dif(i, n);
if (temp < dif) {
dif = temp;
ans = i;
}
}
printf("%d\n", ans);
return 0;
}
|
cs |
완전 탐색으로 풀었다. 의외로 시간 초과가 아니여서 놀랐다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
#include<stdio.h>
#include<stdlib.h>
#pragma warning(disable:4996)
#pragma warning(disable:6031)
int arr[20000];
int cmp(const void* num1, const void* num2) {
return *(int*)num1 - *(int*)num2;
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
qsort(arr, n, sizeof(int), cmp);
printf("%d\n", n % 2 == 1 ? arr[(n + 1) / 2 - 1] : arr[n / 2 - 1]);
return 0;
}
|
cs |
다른 분의 코드를 보니 중앙값을 출력하는 문제인 것 같다.
왜 중앙값이 정답인지는 잘 모르겠다;;;
'백준 온라인 저지 (BOJ) 문제풀이' 카테고리의 다른 글
백준 온라인 저지 (BOJ) 4108 지뢰찾기 (0) | 2020.09.23 |
---|---|
백준 온라인 저지 (BOJ) 16198 에너지 모으기 (0) | 2020.09.23 |
백준 온라인 저지 (BOJ) 18422 Emacs (0) | 2020.09.23 |
백준 온라인 저지 (BOJ) 10819 차이를 최대로 (0) | 2020.09.23 |
백준 온라인 저지 (BOJ) 1764 듣보잡 (0) | 2020.09.23 |