Chapter8. μ΄μ§ νμ
[λ¬Έμ 29] μ
κ΅μ¬μ¬ - Level3
nλͺ
μ΄ μ
κ΅μ¬μ¬λ₯Ό μν΄ μ€μ μμ κΈ°λ€λ¦¬κ³ μμ΅λλ€. κ° μ
κ΅μ¬μ¬λμ μλ μ¬μ¬κ΄λ§λ€ μ¬μ¬νλλ° κ±Έλ¦¬λ μκ°μ λ€λ¦
λλ€.
μ²μμ λͺ¨λ μ¬μ¬λλ λΉμ΄ μμ΅λλ€. ν μ¬μ¬λμμλ λμμ ν λͺ
λ§ μ¬μ¬λ₯Ό ν μ μμ΅λλ€. κ°μ₯ μμ μ μλ μ¬λμ λΉμ΄ μλ μ¬μ¬λλ‘ κ°μ μ¬μ¬λ₯Ό λ°μ μ μμ΅λλ€. νμ§λ§ λ 빨리 λλλ μ¬μ¬λκ° μμΌλ©΄ κΈ°λ€λ Έλ€κ° κ·Έκ³³μΌλ‘ κ°μ μ¬μ¬λ₯Ό λ°μ μλ μμ΅λλ€.
λͺ¨λ μ¬λμ΄ μ¬μ¬λ₯Ό λ°λλ° κ±Έλ¦¬λ μκ°μ μ΅μλ‘ νκ³ μΆμ΅λλ€.
μ
κ΅μ¬μ¬λ₯Ό κΈ°λ€λ¦¬λ μ¬λ μn, κ° μ¬μ¬κ΄μ΄ ν λͺ
μ μ¬μ¬νλ λ° κ±Έλ¦¬λ μκ°μ΄ λ΄κΈ΄ λ°°μ΄ timesκ° λ§€κ°λ³μλ‘ μ£Όμ΄μ§ λ, λͺ¨λ μ¬λμ΄ μ¬μ¬λ₯Ό λ°λλ° κ±Έλ¦¬λ μκ°μ μ΅μκ°μ returnνλλ‘ solution ν¨μλ₯Ό μμ±ν΄μ£ΌμΈμ.
[μ νμ¬ν]
- μ
κ΅μ¬μ¬λ₯Ό κΈ°λ€λ¦¬λ μ¬λμ 1λͺ
μ΄μ 1,000,000,000λͺ
μ΄νμ
λλ€.
- κ° μ¬μ¬κ΄μ΄ ν λͺ
μ μ¬μ¬νλλ° κ±Έλ¦¬λ μκ°μ 1λΆ μ΄μ 1,000,000,000λΆ μ΄νμ
λλ€.
- μ¬μ¬κ΄μ 1λͺ
μ΄μ 100,000λͺ
μ΄νμ
λλ€.
[λ¬Έμ νμ΄]
- μμλ‘ μ£Όμ΄μ§ μκ°λ§νΌ λͺ λͺ
μ μ¬μ¬ν μ μμμ§ κ³μ°
(μ€κ°μ λ¨λ μκ° μμ΄ κ°λ₯ν λͺ¨λ μ¬μ¬λλ₯Ό μ¬μ©νμ λ μ΅λ λͺ λͺ
μ μ¬μ¬ν μ μλμ§ νμΈ)
[μ½λμμ±]
- 0λΆλΆν° κ°μ₯ μ€λ 걸리λ μμ μκ°μ μμκ³Ό λμΌλ‘ μ§μ
def solution(n, times):
answer = 0
left, right = 1, max(times) * n
- μμκ³Ό λμ μ€κ° μκ°μμ μ΅λ λͺ λͺ
μ¬μ¬ν μ μμμ§ κ³μ°
while left <= right:
mid = (left + right) // 2
people = 0
test = []
for time in times:
people += mid // time
if people >= n:
break
- μ¬μ¬ν΄μΌ ν μ¬λμ μ«μλ³΄λ€ λ§μΌλ©΄ λμ ν¬κΈ° μ€μ΄κ³ , μ μΌλ©΄ μμμ ν¬κΈ°λ₯Ό μ€μ¬ μ΄μ§ νμ μν
if people >= n:
answer = mid
right = mid - 1
elif people < n:
left = mid + 1
[μ 체μ½λ]
def solution(n, times):
answer = 0
left, right = 1, max(times) * n
while left <= right:
mid = (left + right) // 2
print(mid, end=')')
people = 0
for time in times:
people += mid // time
if people >= n: break
if people >= n:
answer = mid
right = mid - 1
elif people < n:
left = mid + 1
return answer