[백준] 1654번: 랜선 자르기 / 파이썬

문제 링크

---

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

풀이 코드

---

n, k = map(int, input().split())   
l = [int(input()) for x in range(n)]

mini = 1   # 최소 길이
maxi = max(l)   # 최대 길이

while mini <= maxi:   # mini 가 maxi 보다 작을 동안
    mid = (mini + maxi) // 2   # 중간 값
    su = 0   # 잘라진 랜선의 개수

    for i in l:
        su += i // mid   # 랜선을 중간값으로 잘랐을 때, 잘라진 랜선의 개수
    
    if su >= k:   # 필요한 랜선의 개수 이상을 만들 수 있으면
        mini = mid + 1   # 중간값을 높인다.
    else:   # 필요한 랜선의 개수를 만들 수 없으면
        maxi = mid - 1   # 중간값을 낮춘다

print(maxi)

코드 해석

---

이분 탐색을 활용하였다.

이분 탐색에 대하여 자세히 알고 싶으면 아래 글 참고.

https://code-angie.tistory.com/3

[알고리즘 / Python] 이분 탐색 / 이진 탐색 (Binary Search)

우선 먼저 start를 mini로 잡고 end를 maxi로 잡았다(왜 그랬는지 모르겠다. 걍 이름 통일 할 걸).

그리고 위 문서에 나와 있듯이 반으로 나누고 앞 뒤에서 타겟을 찾는 행위를 반복한다.

타겟이 중간값보다 작다면 중간값을 뒤로 한칸, 크다면 앞으로 한칸.

그런식으로 찾아나가면 된다!