[백준 1654번 문제, 파이썬3] 랜선 자르기

문제

---

코드

 

이분 탐색으로 작성된 코드

import sys

k, n = map(int, sys.stdin.readline().split())
lan_list = sorted([int(sys.stdin.readline()) for _ in range(k)])

max_len = max(lan_list)
min_len = 1

answer = 0

while min_len <= max_len:
    mid_len = (max_len + min_len) // 2
    count = sum([lan // mid_len for lan in lan_list])

    if count >= n:
        answer = mid_len
        min_len = mid_len + 1

    else:
        max_len = mid_len - 1

print(answer)

 

시간초과 나온 코드

import sys

k, n = map(int, sys.stdin.readline().split())
lan_list = [int(sys.stdin.readline()) for _ in range(k)]
div = sum(lan_list) / n

while True:
    div_list = [int(i / div) for i in lan_list]
    if sum(div_list) != n:
        div -= 1
    else:
        break

print(int(div))

---

해결

랜선의 길이를 담은 리스트를 만들고 리스트의 최댓값을 구한다.

최솟값은 1

 

최댓값과 최솟값의 중간값을 구하고 해당 값을 기준으로 랜선을 잘라서 만들 수 있는 개수를 구한다.

중간값을 각각의 랜선에 나누면 값이 나오는데 이걸 전부 더하면 몇개가 만들어지는지 알 수 있다.

 

이렇게 더해진 값이 n보다 크면 answer에 저장하고 최솟값을 중간값에 1을 더한 값으로 변경한다

n보다 작으면 최댓값을 중간값에 1을 빼서 변경한다

 

이러한 반복을 최솟값이 최댓값보다 작거나 같을 때 까지 반복해서 최종적으로 answer를 반환하면 된다

 

---

참고

링크