떡볶이 떡 만들기

 

유형 파악 및 구현

떡의 최대 개수는 백만이고

요청한 떡의 최대 길이는 20억이다.

즉, 떡 백만개에 대해서 0부터 20억 사이의 값으로 잘랐을 때, 원하는 길이가 나와야되고 안나온다면 가장 가까운 값을 출력해야하는 문제이다.

 

만약, 자르는 길이 선정을 순차적 탐색으로 이를 구현한다고 했을 때,

1cm단위로 자르다 20억cm단위까지 잘라봐서 떡의 길이의 합이 m일 때 멈춘다.

최악의 경우 20억*100만의 연산을 한다. 시간 복잡도는 O(N*M)

 

반대로, 이진탐색으로 자르는 길이를 탐색한다면, 

정렬을 할 필요는 없으므로, 정렬에 대한 연산 비용이 들지 않으니 고려하지 않고

시간 복잡도는 O(M*logN)이다. 따라서 이 문제는 무조건 이진탐색을 사용해야 한다.

 

 

 

코드

n = 4
m = 7
arrays = [19, 15, 10, 17]

max_index = max(arrays)
min_index = 0
while max_index >= min_index:
    result = 0
    mid_index = (max_index+min_index)//2
    for array in arrays:
        if array - mid_index > 0:
            result += array-mid_index
    if result < m:
        max_index = mid_index-1
    else:
        min_index = mid_index+1
print(mid_index)