백준 1654번 : 랜선 자르기

<문제>

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

1654번: 랜선 자르기

---

<코드>

import sys
input = sys.stdin.readline

K, N = map(int, input().split())
lan = [int(input()) for _ in range(K)]
res = 0
s, e = 1, max(lan)

while e-s >= 0:
    num = 0
    mid = (s+e)//2
    for i in range(K):
        num += lan[i] // mid
    if num >= N:
        s = mid+1
    else:
        e = mid-1
    res = e
print(res)

---

<풀이>

• 이분 탐색을 위해 최소값 1, 최대값을 변수로 설정한다.
• 각 랜선의 길이에 mid값을 나누어 특정 값에 따라 만들 수 있는 랜선의 개수를 구한다.
• 필요한 랜선 개수보다 많은 경우와 적은 경우로 나누어 생각한다.
• 필요한 랜선의 개수와 비교하여 start와 end 값을 변경해준다.

---

참고 : https://github.com/Junuux/Algorithm/tree/main/Silver/1654