[알고리즘/이분 탐색] 1654번 : 랜선 자르기 - python

링크 : https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

 

---

• 문제
• 소요시간: 23분 26초

---

• 설계하기(접근방법) 

 

1. 입력받기

랜선 길이를 입력받는다

 

2. 구현하기

처음에 랜선을 못 자르는 경우가 있으면

안될 것 같다고 자의적으로 판단해서

실패했다

 

그러나 자르지 않고 넘어가도 된다는 것을 알고

 

end 값을 max(lan_list)로 정했다

start 값은 1부터 시작하면 된다

 

나머지 부분은 

cnt에

랜선을 mid로 나눈 몫을 더해나가면서

이분 탐색을 진행해주면 된다

 

 

3. 출력하기

end를 출력한

 

 

---

• 코드(출력)

import sys

input = sys.stdin.readline

n, need = map(int, input().split())
lan_list = [int(input()) for  _ in range(n)]


start = 1
end = max(lan_list)

while start <= end:
    cnt = 0
    mid = (start + end) // 2
    for i in lan_list:
        cnt += (i // mid)
    if cnt >= need :
        start = mid + 1
    else:
        end = mid - 1
print(end)

 

---

• 얻어갈 부분

1. 이분 탐색의 경우 지문을 주의해서 읽어야 한다