[결정 알고리즘] 랜선자르기

📍 이분검색



검색 범위를 반으로 줄여가며 찾는 방법

자료를 반으로 나누어 반만 탐색하는 것으로 특정 범위 내에 답이 있다는 것이 특징이다



ex)



1~1000 에 해당하는 자료가 있을 때,

① 1~500 / 501~1000 으로 나누고 원하는 output이 1~500 범위 내에 있다면

② 1~500 을 1~250 / 251~500으로 나누고 원하는 output이 251~500 범위 내에 있다면

…



이를 반복하는 탐색이다.

이때 시작 위치와 종료 위치가 변화하기 때문에 코드를 짤 때 주의해야 한다.

 

 

📌

 

# problem: https://www.inflearn.com/course/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8

 

 

< input >

 

4 11

802

743

457

539

 

 

✔️ code

 

import sys
sys.stdin=open("input.txt", "r")

#결정 알고리즘
#특정 범위 내에 답이 있다.
#범위를 좁혀가는 과정
#범위를 좁히고 이분검색

def Count(len): #랜선 개수를 세는 함수
    cnt=0	#랜선 개수
    for x in Line:
        cnt+=(x//len)
    return cnt

k, n=map(int, input().split())
Line=[int(input()) for _ in range(k)]
res=0
largest=max(Line)

#Line과 largest를 정의하는 다른 방법
'''
largest=0
for i in range(n):
    tmp=int(input())
    Line.append(tmp)
    largest=max(largest, tmp)
'''

lt=1	#시작 위치
rt=largest	#종료 위치

while lt<=rt:
    mid=(lt+rt)//2
    
    if Count(mid)>=n:   #랜선 개수가 11개 이상일 때
        res=mid
        lt=mid+1
    else:   #랜선 개수가 11개 미만일 때 (긴 쪽을 무시)
        rt=mid-1
print(res)

 

 

>>>

 

풀면서 정말 막막했던 랜선 자르기 문제

이분탐색 시작과 종료를 어떻게 해야하는지 은근 헷갈렸고

분명 학교 알고리즘 수업에서 들었는데 실제 문제에 적용하려니 어려웠다.

범위를 설정하는 것이 중요한 문제인 듯!