-
[λ°±μ€] 2548 λν μμ°μ with PythonPS 2022. 7. 12. 15:52728x90λ°μν
π BOJ 2548 λν μμ°μ
π‘ 쑰건
- μ 보μ΄λ±νκ΅μ μ°μλ μ¬λ¬ κ°μ μμ°μκ° μ£Όμ΄μ‘μ λ, μ΄λ₯Ό λνν μ μλ λν μμ°μμ λνμ¬ μ°κ΅¬νμλ€.
κ·Έ κ²°κ³Ό μ΄λ€ μμ°μκ° λ€μκ³Ό κ°μ μ±μ§μ κ°μ§λ©΄ λν μμ°μλ‘ μ λΉν κ²μ΄λΌκ³ νλ¨νμλ€.
βλν μμ°μλ μ£Όμ΄μ§ λͺ¨λ μμ°μλ€μ λνμ¬ κ·Έ μ°¨μ΄λ₯Ό κ³μ°νμ¬ κ·Έ μ°¨μ΄λ€ μ 체μ ν©μ μ΅μλ‘ νλ μμ°μμ΄λ€.β
- μλ₯Ό λ€μ΄ μ£Όμ΄μ§ μμ°μλ€μ΄ [4, 3, 2, 2, 9, 10]μ΄λΌ νμ.
μ΄λ λν μμ°μλ 3 νΉμ 4κ° λλ€.
μλνλ©΄ (4μ 3μ μ°¨μ΄) + (3κ³Ό 3μ μ°¨μ΄) + (2μ 3μ μ°¨μ΄) + (2μ 3μ μ°¨μ΄) + (9μ 3μ μ°¨μ΄) + (10κ³Ό 3μ μ°¨μ΄) = 16,
(4μ 4μ μ°¨μ΄) + (3κ³Ό 4μ μ°¨μ΄) + (2μ 4μ μ°¨μ΄) + (2μ 4μ μ°¨μ΄) + (9μ 4μ μ°¨μ΄) + (10κ³Ό 4μ μ°¨μ΄) = 16μΌλ‘ κ°λ€.
- 첫째 μ€μλ μμ°μμ κ°μ Nμ΄ μ
λ ₯λλ€. Nμ 1 μ΄μ 20,000 μ΄νμ΄λ€.
λμ§Έ μ€μλ Nκ°μ μμ°μκ° λΉμΉΈμ μ¬μ΄μ λκ³ μ λ ₯λλ©°, μ΄ μλ€μ λͺ¨λ 1 μ΄μ 10,000 μ΄νμ΄λ€.
- μ΄λΆνμ, μ λ ¬ μ νμ λ¬Έμ
π₯ μμ€ μ½λ
from sys import stdin n = int(stdin.readline()) arr = list(map(int, stdin.readline().split())) arr.sort() l, r = 0, n res = int(1e9) ans = max(arr) while l <= r: mid = (l + r) // 2 temp = sum([abs(x - arr[mid]) for x in arr]) if temp <= res: ans = min(ans, arr[mid]) res = temp r = mid - 1 else: l = mid + 1 print(ans)
π μμ λ° μ€νκ²°κ³Ό
μμ
6 4 3 2 2 9 10
μ€νκ²°κ³Ό
3
β¨οΈ λ¬Έμ νμ΄
- μ΄ λ¬Έμ λ μ΄λΆνμ λ¬Έμ μ΄λ€. Nμ΄ μ΅λ 20000 μ΄κ³ , κ° μ«μμ μ°¨μ΄λ₯Ό μΌμΌν ꡬνλ©΄ λ°λμ TLE μ΄λ€.
- μ΅μκ°μ 0μΌλ‘, μ΅λκ°μ int(1e9)λ‘ λ λ€, μ΄λΆνμμ ν΅ν΄μ mid κ°μ μ ν΄μ€λ€
- μ ν΄μ€ mid κ°μΌλ‘ μ λ ₯λ°μ 리μ€νΈμ κ° μμκ°κ³Όμ μ°¨μ΄λ₯Ό λν΄ μ΅μκ° λλμ§ κ³μ°νλ€.
- κ³μ°ν λν μμ°μκ° κΈ°μ‘΄μ λν μμ°μλ³΄λ€ μλ€λ©΄ κ°±μ ν΄μ€λ€.
λ°μν'PS' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[λ°±μ€] 14494 λ€μ΄λλ―Ήμ΄ λμμ? with Python (0) 2022.07.14 [λ°±μ€] 3079 μ κ΅μ¬μ¬ with Python (0) 2022.07.14 [λ°±μ€] 1939 μ€λμ ν with Python (0) 2022.07.12 [λ°±μ€] 1068 νΈλ¦¬ with Python (0) 2022.07.07 [λ°±μ€] 17103 골λλ°ν νν°μ with Python (0) 2022.07.06 - μ 보μ΄λ±νκ΅μ μ°μλ μ¬λ¬ κ°μ μμ°μκ° μ£Όμ΄μ‘μ λ, μ΄λ₯Ό λνν μ μλ λν μμ°μμ λνμ¬ μ°κ΅¬νμλ€.