[Python] 백준 알고리즘 1654번 : 랜선 자르기

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

1654번: 랜선 자르기

 

 

 

👩‍💻문제 이해

만들 수 있는 랜선의 길이 (target) 이 [1,2,3, ..., 주어진 랜선의 최대값] 배열을 이분탐색을 이용해 (주어진 랜선 길이 // 배열의 중간값)의 합이 K와 같아질 때 까지 반복하면 된다.

 

정렬된 배열에서 각각의 (주어진 랜선 길이 // start와 end의 중간값(mid)) 의 합(= cnt)이 k와 같아질 때까지 이분탐색 알고리즘을 반목하면 된다. 이 때 start는 자를 수 있는 최소길이 1이고 end는 배열의 최대값이다.

 

이 때 자를 수 있는 랜선의 최대값을 구해야 하므로, 최종 return 값은 K와 같아질 때의 end (배열의 마지막 인덱스)가 된다.

 

 

 

 

👩‍💻반복문을 사용해 이분탐색 알고리즘 구현 (함수 별도 구현)  : 성공🌈

# 1654번 : 랜선 자르기
# 반복문 + 함수 별도로 구현

import sys
k,n = map(int, sys.stdin.readline().split())
li = []
for i in range(k):
  li.append(int(sys.stdin.readline()))
li = sorted(li)

def binary(n, arr, cnt):
  start = 1
  end = max(arr)

  while start <= end :
    cnt = 0
    mid = (start + end) // 2
    for i in arr:
      cnt += (i // mid)
    
    if cnt >= n:
      start = mid + 1
    
    else:
      end = mid - 1

  return end

print(binary(n, li, 0))

 

 

👩‍💻반복문을 사용해 이분탐색 알고리즘 구현 (함수 X)  : 성공🌈

import sys

k,n = map(int, sys.stdin.readline().split())
li = []
for i in range(k):
  li.append(int(sys.stdin.readline()))
li = sorted(li)

start = 1
end = max(li)

while start <= end: 
    mid = (start + end) // 2 
    cnt = 0 
    for i in li:
        cnt += i // mid 
        
    if cnt >= n: 
        start = mid + 1
    else:
        end = mid - 1
print(end)

 

 

 

✨Point✨

N 만큼 list에 원소 추가 시키기 한 줄로 쓰는 법
- > li = [int(input()) for _ in range(N)]

반복문을 사용한 이분탐색에서 반복 조건은
while start <= end :
로 생각하는게 편함

이분 탐색 알고리즘에서는 언제 왼쪽 범위 또는 오른쪽 범위로 이동할 것인지, 
if 문의 조건이 중요!

가능한 최대의 것을 구하고자 할 때 -> return end
가능한 최소한의 것을 구하고자 할 때 -> return start