[백준 1654번] 랜선 자르기

📖문제:

 

📙풀이:

처음 알고리즘을 짤 때는 가능한 큰 수(가지고 있는 모든 랜선의 합 / 필요한 랜선 개수)에서 -1씩 빼가며 찾는 방법으로 코드를 짰다.

하지만 바로 시간초과..

그래서 이진 탐색으로 절반씩 범위를 줄여가면서 가능한 가장 큰 랜선 토막의 길이를 찾는 방법으로 코드를 짰다. 

시간복잡도: O(log(N))

 

✏️코드:

'''
https://www.acmicpc.net/problem/1654
문제: 랜선 자르기
난이도: 실버2
'''

# 이진 탐색으로 풀어야 됨!
import sys

line_num, need = map(int, input().split())
lines = []
for _ in range(line_num):
    lines.append(int(sys.stdin.readline()))

possible_max = int(sum(lines) / need)
index_min = 0
index_max = possible_max
answer = 0

while index_min <= index_max:
    sum = 0
    middle = (index_min + index_max) // 2
    if middle == 0:
        middle = 1
    
    for i in lines:
        sum += i // middle
    
    if sum >= need:
        index_min = middle + 1
    else:
        index_max = middle - 1
    
print(index_max)

 

🔗링크:

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