[Baekjoon, Python] 1654번: 랜선 자르기

도입

백준 단계별 풀기, 이분탐색 세 번째 문제이다.

백준 1654번 문제, 입력, 출력

---

백준 1654번 입출력 예제 1

---

풀이

1. K(영식이가 가진 랜선)개의 랜선들 중 가장 높은 값과 가장 낮은 값을 정해서 이분탐색 알고리즘으로 가장 높은 값과 낮은 값의 중간을 설정해가면서 N개를 맞추는 로직이다.

 

2. 자투리는 버리는 것이기 때문에, //의 산술연산자를 통해 몫만 챙긴다. 

 

3. while문을 돌면서 중간 count로 몇 개의 랜선이 나오는지 확인한다. 

 

4. N(만족해야하는 랜선 수)가 도달하지 않는다면, 길이를 좀 더 줄여봐야 한다. high_l 에 mid_l -1 을 대입해 줄인다. 

---

코드

from sys import stdin

K, N = map(int,stdin.readline().split())
list_K = list(map(int,stdin.readlines()))
high_l, low_l = sum(list_K)//N, 1       # Key point 

while low_l <= high_l :                 # 로우 <= 하이
    mid_l = (high_l + low_l)//2         # 중간 값
    count = sum([x//mid_l for x in list_K])   # list_K를 mid값으로 나눈 몫 (예제1 -> 4+3+2+2)
    if count  < N:                         # N을 못채운 경우
        high_l = mid_l - 1
    elif count >= N:                      # N을 채우거나 넘긴경우 (합격)
        low_l = mid_l + 1
        rtn = mid_l

print(rtn)

---

마무리

생각보다 할 만한 알고리즘이다. 파이썬으로 알고리즘을 푸는데 있어서 가장 많이 도움을 받고 있는 블로그가 하나 있다. 차밍이님(chancoding) 블로그인데, 알고리즘을 짜더라도 어떻게 효율적으로 짤 수 있는지, 시간복잡도를 더 줄이는 방법등을 많이 배우는 것 같다. 이분탐색부터 해당 블로그를 보고 있는데 정말 도움을 많이 받는 것 같아 구독과 좋아요를 했다! 

 

1. import sys 를 필요한 stdin만 import를 하는 것.

2. input을 통해 입력을 받는 것이 아닌, stdin.readline()으로 받는 것. 

등등...