이것이 코딩테스트다 with 파이썬 - Chp 7. 이진 탐색_3. 떡볶이 떡 만들기

Try1

n, m = map(int, input().split())
rice_length = list(map(int, input().split()))
rice_length.sort()
max = rice_length[-1]
result = 0
target = [0]*n

while result <= m:
    for idx, value in enumerate(rice_length):
        if max == value:
            target[idx] = value
    max -= 1
    # value -= 1
    target[idx] -= 1
    result += 1
print(result)

적어도 M만큼의 떡을 집에 가져가기 위해 절단기에 설정할 수 있는 높이의 최댓값을 출력하는 것이 조건인데, M의 값을 정답으로 도출하여서 오답.
-> 문제가 요구하는 바를 정확하게 파악하고 문제풀이 시작해야함.

Try2

n, m = map(int, input().split())
rice_length = list(map(int, input().split()))
rice_length.sort()
max = rice_length[-1]
result = 0
target = [0] * n

while result < m:
    for idx, value in enumerate(rice_length):
        if max == value:
            target[idx] += 1
            rice_length[idx] -= 1
    max -= 1
    result = sum(target)
print(max)

정답은 도출되었으나, 데이터의 양이 많을 경우(대략 10억개 이상) 이진탐색으로 풀어야 코딩테스트내의 시간 조건을 맞출 수 있다.

Try3

n, m = map(int, input().split())
rice_length = list(map(int, input().split()))

start_idx = 0
end_idx = max(rice_length)

result = 0

while (start_idx <= end_idx):
    mid_idx = (start_idx + end_idx) // 2
    cutting_rice = 0

    for each_length in rice_length:
        if each_length > mid_idx:
            cutting_rice += each_length - mid_idx

    if cutting_rice >= m:
        result = mid_idx
        start_idx = mid_idx + 1
    else:
        end_idx = mid_idx - 1

print(result)

예시 답안

# 떡의 개수(N)와 요청한 떡의 길이(M)을 입력받기
n, m = list(map(int, input().split(' ')))
# 각 떡의 개별 높이 정보를 입력받기
array = list(map(int, input().split()))

# 이진 탐색을 위한 시작점과 끝점 설정
start = 0
end = max(array)

# 이진 탐색 수행(반복적)
result = 0
while(start <= end):
    total = 0
    mid = (start + end) // 2
    for x in array:
        # 잘랐을 때의 떡의 양 계산
        if x > mid:
            total += x - mid
    # 떡의 양이 부족한 경우 더 많이 자르기(왼쪽 부분 탐색)
    if total < m:
        end = mid - 1
    # 떡의 양이 충분할 경우 덜 자르기(오른쪽 부분 탐색)
    else:
        result = mid # 최대한 덜 잘랐을 때가 정답이므로, 여기에서 result에 기록
        start = mid + 1
# 정답 출력
print(result)