99클럽 코테 스터디 2일차 TIL Boj 1654. 암기왕

Approach 1

• 랜선을 잘라내면서, target number를 찾는 것과 정수가 1,000,000 이하기 때문에 이분 탐색이라고 생각했다.
• N개 이상되는 count를 갖는 값을 찾기 위해 min_length를 하나씩 올려주면서 찾았다.

---

Solution 💡

import sys

N, M = map(int, sys.stdin.readline().split())

lst = []
for _ in range(N):
    lst.append(int(sys.stdin.readline().strip()))

max_length = max(lst)
min_length = 1

while min_length <= max_length:

    mid = (min_length + max_length) // 2
    count = 0

    for num in lst:
        count += num // mid
    
    if count >= M:
        min_length = mid + 1
    else:
        max_length = mid - 1

print(min_length-1)

• 처음에 최소 값을 출력하는 것이라 min_length 값을 출력했었는데, 생각해보니 mid값이 자르는 길이의 최소 값이기 때문에 -1 해주었다.