백준 랜선자르기(1654번) 파이썬 풀이

이진탐색 카테고리에 속한 문제

 

정답코드

K, N=map(int,input().split())
cable_list=[]
for _ in range(K):
    cable_list.append(int(input()))

def how_many_cable(cable_size, cable_list):
    cable_num=0
    for cable in cable_list:
        cable_num+=(cable//cable_size)
    return cable_num

def binary_search(K, cable_list, target):
    
    low=1
    high=max(cable_list)

    while low<=high:
    
        middle=(low+high)//2
        if middle==high:
            return middle

        cn1=how_many_cable(middle,cable_list)
        cn2=how_many_cable(middle+1,cable_list)

        if (cn1>=target) & (cn2<target):
            return middle

        elif cn1<target:
            high=middle-1
            
        elif cn1>=target:
            low=middle+1


print(binary_search(K,cable_list, N))

---

 

햇갈렸던 포인트

이진탐색의 범위

이진탐색의 주제는 적절한 랜선의 길이이다

이진탐색의 범위를 `0~가장긴랜선의 길이`로 설정하였다

모든 랜선을 사용할필요는 없다, 다음예제가 이해를 도울것이다

2 4
1
100

N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다

문제를 꼼꼼하게 읽고 풀이에 들어가야하는 이유가 여기에 있는것같다(나는 이부분을 놓쳤다)

다음예제가 이해를 도울것이다

3 5
100
200
300

길이가 100일때 N은 6, 길이가 101일때 N은 3이다 따라서 답은 100이된다

---

이진탐색

이진탐색의 종료조건은 다음과 같다

low<=high

이진탐색범위안에서 조건을 만족하는 랜선크기를 찾지못하였을때

하지만 문제에서 항상 K<=N이라고 하였기때문에 조건을 만족하는 랜선크기는 반드시 존재한다

 

(cn1>=target) & (cn2<target)

 

cn1은 middle의 길이로 만들수있는 케이블의 개수, cn2는 middle+1의 길이로 만들수있는 케이블의 개수이다

cn1이 cn2의 값이 N을 기준으로 나뉠때 middle의 길이를 return하며 이진탐색은 종료된다

 

middle==high:

middle이 high와 같을 경우 답이 high이거나 아니면 범위안에 답이 없는경우 두가지 경우밖에 존재하지않는다 

다만 위에서 답은 반드시 존재한다고 하였으므로 이런상황에서 middle을 return하게된다

 

elif cn1<target:
    high=middle-1

elif cn1>=target:
    low=middle+1

위 3가지 상황을 제외한 나머지 경우에 대해서는 계속 탐색을 이어나간다