[BOJ] 1654: 랜선 자르기

[BOJ 1654: 랜선 자르기] 문제 바로가기

 

❓문제 설명

❗️문제 풀이

이분탐색을 이용하여 풀었다.

[1, 최대 랜선 길이]를 start, end값으로 시작해 중간값(mid)을 구했다.

이 후, 해당 중간값으로 구할 수 있는 랜선의 개수를 N과 비교해 start, end 값을 각각 조절했다.

if lan_num >= N:
    start = mid + 1
else:   # lan_num < N
    end = mid - 1

해당 풀이 전, _최댓값_이라는 단어에 집중하여 랜선의 개수가 N과 같을 때

lan_num == N 을 조건문에 추가하여 새로운 리스트에 mid를 추가하고,

이 중 최댓값을 출력하는 방법을 이용했다.

    if lan_num > N:
        start = mid + 1
    elif lan_num == N:
        list_.append(mid)
        start = mid + 1
    else:   # lan_num < N
        end = mid - 1

print(max(list_))

하지만 K가 N보다 큰 경우, list에 추가하는 조건을 무조건 통과하기 때문에 빈 리스트에서 max() 값을 찾는 오류가 발생했다.

📌전체 코드

# bOJ 1654 랜선 자르기

import sys
K, N = map(int, sys.stdin.readline().split())
lan_list = []
for i in range(K):
    lan_list.append(int(sys.stdin.readline().rstrip()))

start, end = 1, max(lan_list)
while start <= end:
    mid = (start + end) // 2
    lan_num = 0
    for lan in lan_list:
        lan_num += lan // mid
    
    if lan_num >= N:
        start = mid + 1
    else:   # lan_num < N
        end = mid - 1

print(end)

해당 코드를 통해, 랜선의 최대 길이를 구할 수 있다.