<aside> 🔥 백준 1654번 문제 링크

</aside>

<aside> 🔥 문제 정리

캠핑갈때 쓸 n개의 랜선을 만들어야한다.

자체적으로 k개의 랜선을 가지고 있다.

k개의 랜선을 모두 같은 n개의 랜선으로 만들고 싶다.

첫째줄에 k개의 가지고 있는 랜선 개수와 n개의 만들고자 하는 랜선 개수가 주어진다.

k줄에 걸쳐 가지고 있는 랜선의 길이가 주어진다.

n개의 랜선을 만드려면 k개의 랜선을 몇cm로 잘라야하는지 출력해라.

# 입력값
4 11
802
743
457
539

# 출력값
200

# 설명
802 -> 200으로 4개 나옴
743 -> 200으로 3개 나옴
457 -> 200으로 2개 나옴
539 -> 200으로 2개 나옴
총합으로 11개. 따라서 정답은 200

</aside>

<aside> 🔥 이전에 풀어보았던 이진 탐색 문제들과 상당히 유사하다.

0부터 리스트의 가장 큰 길이를 이진 탐색하며 자를 길이를 구한 뒤,

랜선을 잘라서 개수를 목표치와 비교한다.

목표치보다 많을 경우에는 범위를 오른쪽으로 좁혀 길이를 높힌다.

목표치보다 적을 경우 범위를 왼쪽으로 좁혀 길이를 낮춘다.

</aside>

<aside> 🔥 코드 진행

(1) 입력값을 받아 자를 길이의 하한과 상한을 지정한다.

import sys

def input():
    return sys.stdin.readline().strip()

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

lo = 0              # 하한선 0으로 지정
hi = max(arr)       # 최대값으로 상한선 지정

(2) 하한선이 상한선을 넘어가지 않는선에서 반복하여 진행,

자른 랜선의 개수를 담을 total을 지정한다.

랜선의 범위 중 중간값 mid를 지정해준다.

# 하한선이 범위안에서 반복
while lo <= hi:
    total = 0               # 전체 값
    mid = (lo + hi) // 2    # 중간 값 지정

(3) 리스트를 순회하며 중간값으로 자른 개수를 구하여 total에 저장한다.

<aside> 🔥 여기서 ZeroDivisionError 가 발생하는 경우가 있어서 예외처리를 넣었다.

mid가 0인 경우에는 예를들어 10//0의 경우 해당 오류가 발생한다.

</aside>

for x in arr:
  if x >= mid:    # 자르고자 하는 길이보다 클 경우
      try :
          total += x // mid   # 잘라서 total에 자른 랜선 개수 넣기
      # 위에서 mid가 0인경우 그대로 x리턴.
      except ZeroDivisionError :
          total += x

(4) 위에서 얻은 랜선의 개수와 얻고자하는 랜선의 개수를 비교한다.

total이 n보다 작아 개수가 부족할 경우에는 왼쪽으로 탐색한다.

반대의 경우 오른쪽 탐색한다.

# 랜선의 개수가 부족하면 자를 길이를 낮춘다.
    if total < n :
        hi = mid - 1
    # 랜선의 개수가 더 많으면 자를 길이를 높힌다.
    else :
        lo = mid + 1

</aside>