[백준 1654] 랜선 자르기

백준 1654

🔍 알고리즘 분류

• 이분탐색

💡 문제 풀이

백준 2805 나무자르기와 매우 유사한 문제

1. 이분탐색을 위해 초기값 start = 1, end = max(arr)로 설정
   (start = 0로 설정 시 ZeroDivisionError 발생❗️)
2. 리스트 순회하며 랜선 개수 i // mid로 카운트하여 총합 cnt 계산
3. cnt가 n보다 같거나 클 경우 랜선 길이 늘리기 start = mid + 1
4. cnt가 n보다 작을 경우 랜선 길이 줄이기 end = mid - 1

📄 코드

• Python

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

start = 1 # ZeroDivisionError 방지하기 위해 0이 아니라 1로 설정
end = max(arr) # 리스트 중 최댓값
h = end # 최대 길이

# 이분 탐색
while start <= end:
    mid = (start + end) // 2
    cnt = 0 # 만들 수 있는 랜선 수
    
    for i in arr:
        cnt += i // mid # 랜선 수 카운트

    # 생성된 랜선이 많은 경우
    if cnt >= n:
        # 정답 갱신
        h = mid
        # 랜선 길이 늘리기
        start = mid + 1
    else: # 생성된 랜선이 부족한 경우
        # 랜선 길이 줄이기
        end = mid - 1

# 결과 출력
print(h)