랜선자르기

📌 백준 1654번 랜선 자르기 — 이분탐색

---

🧐 문제 해석

• 길이가 다른 k개의 전선을 가지고 길이가 같은 n개의 전선을 만들어야 한다.
• 만들 수 있는 전선 하나의 최대 길이를 구하는 문제.
• 이분 탐색을 통해 "길이"를 기준으로 탐색해야 한다.

---

✅ 일반적인 접근 방식 (정석 풀이)

cut_line(1, max(line))

• 최소 길이: 1부터 시작 (무조건 최소 단위 가능, ZeroDivisionError 예외 처리)
• 최대 길이: 제공된 전선 중 가장 긴 길이

이 방식은 안전하고 단순하지만, 탐색 범위가 넓다는 단점이 있다고 생각했다.

---

💡 내가 생각한 최적화 전략

최대 길이 (max_length) 설정

max_length = sum(line) // n

• 모든 전선 길이를 합쳐도 n개 를 만들수 없으면 그것은 최대 길이가 될 수 없음.
• 그리디 처럼 단순하게 생각한 최대 길이
• 해당 값 이상으로 자른다면 무조건 n개 미만 생성

---

최소 길이 (min_length) 설정

min_num = n // k + 1
min_length = min(line) // min_num + 1

• n // k는 최소의 길이에서 최대한을 뽑아 낸다는 가정 하에 각 전선당 최소한으로 만들어야 하는 개수
• +1은 정수계산으로 인한 보정 값

# 예를 들자:
n = 11, k = 4 → 11 // 4 + 1 = 3 + 1 = 4  
→ 각 랜선에서 **최소 4개씩** 만들어야 전체 n개 만족

• 결국적으로 min(line) // 4 + 1은
  가장 짧은 전선에서도 4개 이상 본다는 조건 아래의 최소 길이

🔹 논리: “가장 짧은 전선에서 min_num 이상 잘라낸다면, 다른 전선에서도 잘라낼 수 있다”

---

🔍 성능적으로 의미 있을까?

• 이분탐색의 시간 복잡도는 O(log N)
• 사실 큰 효과는 없다 !! 하하 !
• 그럼에도 최대한 여러가지로 생각해봤다는 것에 의의를 두려한다.

---

💯 정답

import sys
input = sys.stdin.readline
k,n = map(int,input().split())
line = [int(input()) for _ in range (k)]
length = 0
def how_many_line(cut_length):
    sum = 0
    if cut_length == 0 :
        return
    for x in line :
        sum += x//cut_length
    if sum >= n :
        return True
    else :
        return False

def cut_line(start,end):
    global length호
    if start > end :
        return 
    mid = ( start + end ) // 2
    #길이를 더 늘려야 하는 상황
    if how_many_line(mid) :
        length = max(length,mid)
        cut_line(mid+1,end)
    #길이를 더 줄여야 하는 상황
    else :
        cut_line(start,mid-1)

# max_length = sum(line) // n
# min_num = n//k + 1
# min_length = min(line) // min_num + 1

# cut_line(min_length,max_length)
cut_line(1,max(line))
print(length)