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

풀이

이번문제는 결정알고리즘이다. 결정알고리즘의 특징은 "우리가 찾고자 하는 답이 특정 범위 안에 있다!" 라는 것이다.

그 안에서 이분검색을 통해 중앙 값을 정하고, 그 값이 답이 되는지 판단하는 함수나 조건을 만들어 값을 좁혀나가는 식으로 풀면 된다.

1. 시작점, 끝점을 정해준다.
   ex) lt = 1, rt = max(a)
   
   
2. 시작점과 끝점을 통해 중앙값을 정해준다.
   ex) mid = (lt + rt) // 2
   
   
3. 정한 중앙값으로 전부 나눠준다. (이때 개수를 세는 cnt변수가 필요할 것 같다.)
   
   
4. cnt가 n보다 작다면 -> rt = mid - 1
   cnt가 n보다 크거나 같다면 -> lt = mid + 1
   
   
5. cnt가 크거나 같다면 정답 범위 안에 있기때문에 출력할 변수안에 담아준다.
   
   
6. 반복문의 조건은 lt가 rt보다 작거나 같게 해줌으로써 최대값을 구할수 있게 해준다.

코드

k, n = map(int, input().split())
a = []
for i in range(k):
    a.append(int(input()))

lt = 1
rt = max(a)
res = 0

def Check(a):
    cnt = 0
    for i in a:
        cnt += i // mid
    return cnt

while lt <= rt:
    mid = (lt + rt) // 2
    cnt = 0
    for i in a:
        cnt += i // mid
    tmp = Check(a)
    if tmp >= n:
        res = mid
        lt = mid + 1
    else:
        rt = mid - 1
print(res)