[BOJ] 랜선 자르기(1654) - 그래프

문제 url: https://www.acmicpc.net/problem/1654

난이도: 실버2

정답률:

권장 시간: 분

권장 시간 복잡도:

분류: 이분 탐색, 매개 변수 탐색

 

문제 설명

집에서 시간을 보내던 선영이는 랜선을 자르며 즐거운 시간을 보내고 있다.
선영이의 집에는 K개의 랜선이 있다.

길이가 제각각인 K개의 랜선을 가지고 모두 N개의 같은 길이의 랜선으로 만들고자 한다.
랜선을 자르는 과정에서 손실되는 길이는 없다고 가정하며, 자른 후에도 랜선은 N개로 만들어야 한다.

예를 들어, 300cm짜리 랜선이 있고 이를 140cm 길이로 자른다면, 랜선은 2개가 되고 20cm는 버려지게 된다.
(이미 자른 랜선은 붙일 수 없다.)

이때, 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에는 랜선의 개수 K, 필요한 랜선의 개수 N이 입력된다.
K는 1 이상 10,000 이하의 자연수이고,
N은 1 이상 1,000,000 이하의 자연수이다.
그 다음 K줄에는 각 랜선의 길이가 센티미터 단위로 입력된다.
랜선의 길이는 2³¹ - 1 이하의 자연수이다.

---

출력

첫째 줄에 N개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위로 출력한다.

---

예제 입력 1

4 11  
802  
743  
457  
539

---

예제 출력 1

200

---

내 풀이

# lines 만들기
k, n = map(int,input().split())
lines = []
for _ in range(k):
    lines.append(int(input()))

end = max(lines)
start = 1


while start < end:
  # while문 안에서 cnt를 초기화 시켜줘야함
  cnt = 0
  mid = (start + end) // 2 + 1
  for line in lines:
    cnt += line // mid

  # 성공 -> 후보임 -> 길이를 더 늘려보는 시도를 해봐도 됨
  if cnt >= n:
    # start = mid + 1 // 실패 조건1
    start = mid
  # 실패 -> 길이를 줄여야함
  else:
    end = mid - 1


print(end)

---