[백준] 1654번 파이썬 (랜선 자르기)

1. 문제와 예제

문제

예제

랜선의 최대 길이를 간단하게 구해낼 수 있는 방법이 생각나지 않으므로 탐색하는 문제겠구나를 알 수 있고 효율적으로 찾기 위해 이분탐색을 사용하면 되겠다고 예상할 수 있다.

---

2. 전체 코드

import sys
input = sys.stdin.readline

# 입력 받기
K, N = map(int, input().split()) # 갖고 있는 랜선의 개수, 필요한 랜선의 개수
lst = [int(input().rstrip()) for _ in range(K)] # 랜선 길이 리스트 생성

# 이분탐색 시작
l, r = 1, max(lst) # left, right
while l <= r:
    m = (l + r) // 2 # mid
    cnt = 0 # 만들 수 있는 랜선의 개수
    for i in lst:
        cnt += (i // m)
    if cnt >= N: # 크거나 같은 랜선의 길이가 존재하는 경우
        l = m + 1 # left를 mid로 당김
    else: # 작은 랜선의 길이가 필요한 경우
        r = m - 1 # right를 mid로 당김

# 결과 출력하기
print(r)

---

3. 코드 해설

예상했던 것과 같이 이분탐색을 통해 랜선의 최대 길이를 찾아가면 된다. 추가로 'if cnt >= N'에 'cnt == N'이 포함되는 이유는 필요한 랜선의 개수가 만족되더라도 우리는 랜선의 최대 길이를 찾아야 하기에 더 큰 랜선의 길이가 있는지 left를 mid로 당겨서 계속 탐색해야 한다.