일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 | 31 |
- 사칙연산
- 수학
- 이진탐색
- Image Classification
- 백준
- 논문리뷰
- C++
- 다이나믹프로그래밍
- 정수론
- SQL
- 백준알고리즘
- 이분탐색
- 프로그래머스연습문제
- 논문구현
- 문자열
- 브루트포스알고리즘
- 소수판정
- 정렬
- 큐
- 프로그래머스sql
- 프로그래머스코딩테스트
- 자료구조
- C언어
- 프로그래머스
- 해시를사용한집합과맵
- 그리디
- C
- MySQL
- 그리디알고리즘
- 구현
- Today
- Total
초보 개발자의 이야기, 릿허브
[C++] 백준 2548번 대표 자연수 본문
1. 문제이해
https://www.acmicpc.net/problem/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)
백준의 난이도는 알다가도 모르겠다..
실버인데 골드 정도로 어려운 문제도 있고, 브론즈 정도로 쉬운문제도 있고..😭
문제에 대한 질문이나 지적은 언제나 감사하게 받고 있습니다.😊
'코딩테스트 > 📗 백준 (BOJ)' 카테고리의 다른 글
[C++] 백준 2164번 카드2 (0) | 2022.02.15 |
---|---|
[C++] 백준 2193번 이친수 (0) | 2022.02.14 |
[C++] 백준 1475번 방 번호 (0) | 2022.02.09 |
[C++] 백준 13022번 늑대와 올바른 단어 (0) | 2022.02.07 |
[C++] 백준 1158번 요세푸스 문제 (0) | 2022.02.04 |