백준 BOJ 2548 - 대표 자연수

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

2548번: 대표 자연수

두번속은문제....

 

1. 지문읽으면서 엥 이거 평균아닌가 라고 생각 >> 지문에서반박당함

2. 이분탐색 생각해봄 >> 무한반복 걸려서 고민하던중 다른 아이디어 발견

 

이 문제에서 요구하고 있는 값은 입력된 배열의 중앙값이다.

입력된 배열에서

대표 자연수를 $K$ 라고 할때,

 

대표 자연수보다 큰 수가 $A$개 있고

대표 자연수보다 작은 수가 $B$ 개 있을 것이다.

(이때, $A+B == N$ 이다)

 

대표 자연수 $K$를 1 크게 하면

$A$개의 수와의 차의 절댓값이 1만큼 줄어들어 합 $SUM$이 $A$만큼 줄어들것이고

$B$개의 수와의 차의 절댓값이 1만큼 늘어 합 $SUM$이 $B$만큼 증가할것이다.

 

또한, $K$를 1 작게 하면

$SUM$은 $A$만큼 증가하고 $B$만큼 줄어들것이다.

 

$SUM$을 최소로 정하려면 $A$와 $B$가 같아져서 증가하고 줄어드는 변화가 0에 가까워져야 하고,

$A$ 와 $B$가 같다는 말은 $K$보다 큰 수와 작은 수의 갯수가 같다는 말이므로

정렬된 배열에서 중간에 있는 값에 해당한다.

 

배열의 크기가 짝수일때는 지문에서 요구하는대로 작성해주면 된다.

 

#include<bits/stdc++.h>
using namespace std;

int N;
int arr[23456];

int main(){
	cin.sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> N;
	for(int i=0; i<N; i++){
		cin >> arr[i];
	}
	
	sort(arr, arr+N);
	
	int idx;
	if(N%2) idx = N/2;
	else idx = N/2-1;
	
	cout << arr[idx];
	return 0;
}