결정 알고리즘 (랜선 자르기)

결정 알고리즘을 이용할 때는 이분탐색을 이용하고, 문제에서 보통 답의 범위를 알 수 있다.

 

 

알고리즘은 다음과 같다.

 

주어진 수들 중에서 max를 찾는다. 그럼 범위는 1 ~ MAX의 수가 될 것이고,

 

이분탐색으로 중간값을 찾아 답이 되는지 찾아본다.

 

답이 되는지 찾아보기 위해, Count 함수를 만든다. 이 함수는 주어진 숫자들을 파라미터로

 

받은 값들로 모두 나누었을 때 그 합을 반환한다.

 

반환한 값과 K 값을 비교하여, 반환 값이 더 작으면 답이 될 수 없으므로 중간값 기준 더 작은

 

값, 즉 왼쪽을 탐색해야한다. 반환값이 K값보다 크거나 같을 때는 오른쪽을 탐색한다.

 

그렇게 while문을 반복하며 lt <= rt가 될때까지 반복하다 보면 최적의 닶이 나오게 된다.

 

이분탐색 기반의 가장 기본적인 알고리즘이며, 기본인 만큼 많이 쓰이고 중요한 알고리즘이니,

 

확실하게 익혀둘 필요가 있다고 생각한다. 전체 코드는 다음과 같다.

 

 

import sys

#sys.stdin=open("input.txt", 'rt')

MAX = 0

K, N = map(int, input().split())

lst = []

def Count(num): #총 몇개의 랜선 조각이 나오는지 반환

    cnt = 0

    for i in lst:

        cnt += (i // num)

    return cnt

for i in range(K):

    lst.append(int(input()))

    if lst[i] > MAX:

        MAX = lst[i]

lt = 1

rt = MAX

while lt <= rt:

    mid = (lt+rt) // 2

    if Count(mid) < N:

        rt = mid-1

    else:

        res = mid

        lt = mid+1

print(res)