일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- Binary-Search
- BFS
- codeup
- DP
- backtracking
- bitmask
- C
- floyd_warshall
- bruteforcing
- priority_queue
- string
- PS
- java
- C++
- number_theory
- stack
- Greedy
- queue
- ad_hoc
- sliding-window
- Prefix-Sum
- Python
- Sort
- Constructive
- lazy-propagation
- Dijkstra
- knapsack
- implementation
- math
- segment-tree
- Today
- Total
공작소
[ BOJ ] 2548 : 대표 자연수 ( SILVER 3 ) / Python 본문
문제
정보초등학교의 연아는 여러 개의 자연수가 주어졌을 때, 이를 대표할 수 있는 대표 자연수에 대하여 연구하였다. 그 결과 어떤 자연수가 다음과 같은 성질을 가지면 대표 자연수로 적당할 것이라고 판단하였다.
“대표 자연수는 주어진 모든 자연수들에 대하여 그 차이를 계산하여 그 차이들 전체의 합을 최소로 하는 자연수이다.”
예를 들어 주어진 자연수들이 [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 이하이다.
출력
첫째 줄에 대표 자연수를 출력한다. 대표 자연수가 두 개 이상일 경우 그 중 제일 작은 것을 출력한다.
풀이 과정
N의 제한이 최대 2만이라, 직접 모든 자연수들의 차이를 구하는 N^2 브루트포스 풀이가 아슬아슬하게 통과된다.
import sys
input = sys.stdin.readline
n = int(input().rstrip())
arr = list(map(int, input().rstrip().split()))
res_num = -1
res_value = 0
for i in range(n):
now_value = 0
for j in range(n): now_value += abs(arr[i] - arr[j])
if res_num == -1 or res_value > now_value:
res_num = arr[i]
res_value = now_value
elif res_value == now_value and res_num > arr[i]:
res_num = arr[i]
print(res_num)
'Problem Solving > BOJ' 카테고리의 다른 글
[ BOJ ] 17615 : 볼 모으기 ( SILVER 1 ) / Python (0) | 2024.03.22 |
---|---|
[ BOJ ] 6236 : 용돈 관리 ( SILVER 2 ) / Python (0) | 2024.03.22 |
[ BOJ ] 1456 : 거의 소수 ( GOLD 5 ) / Python (0) | 2024.03.10 |
[ BOJ ] 1929 : 소수 구하기 ( SILVER 3 ) / Python (0) | 2024.03.10 |
[ BOJ ] 16112 : 5차 전직 ( SILVER 2 ) / Python (0) | 2024.03.10 |