2548번: 대표 자연수
첫째 줄에는 자연수의 개수 N이 입력된다. N은 1 이상 20,000 이하이다. 둘째 줄에는 N개의 자연수가 빈칸을 사이에 두고 입력되며, 이 수들은 모두 1 이상 10,000 이하이다.
www.acmicpc.net
[문제]
“대표 자연수는 주어진 모든 자연수들에 대하여 그 차이를 계산하여 그 차이들 전체의 합을 최소로 하는 자연수이다.”
예를 들어 주어진 자연수들이 [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로 위의 두 경우보다 차이들의 합이 더 커짐을 볼 수 있다.
연아를 도와서 위의 성질을 만족하는 대표 자연수를 구하는 프로그램을 작성하시오.
대표 자연수가 두 개 이상일 경우 그 중 제일 작은 것을 출력한다.
[문제 접근]
이중 for문을 돌면서 하나의 자연수와 나머지 자연수들의 차이를 구한다.
이중 리스트로 저장하여 람다 함수로 정렬한다.
[오답]
시간초과...
시간초과...
다른 글을 찾아본 결과 "중앙값"을 사용하여 푸는 문제라고 한다..
무슨 말인지 이해가 아직 되지 않아 나중에 밑 블로그를 참고하여 다시 시도해보기로 하였다!
<중앙값을 사용하여 푼 블로그>
blog.naver.com/jjys9047/222275518234
[백준] 2548. 대표 자연수
문제 정보초등학교의 연아는 여러 개의 자연수가 주어졌을 때, 이를 대표할 수 있는 대표 자연수에 대하여 ...
blog.naver.com
'알고리즘 공부 > 백준 > Python3' 카테고리의 다른 글
| [백준 파이썬] #1934: 최소공배수 (0) | 2021.03.19 |
|---|---|
| [백준 파이썬] #2501: 약수 구하기 (0) | 2021.03.19 |
| [백준 파이썬] #11557: Yangjojang of The Year (0) | 2021.03.15 |
| [백준 파이썬] #4592: 중복을 없애자 (0) | 2021.03.15 |
| [백준 파이썬] #4101: 크냐? (0) | 2021.03.14 |
