떡볶이 떡 만들기

이 문제는 이것이 코딩테스트다 201페이지 문제이다.

이 문제는 구현자체는 쉽지만 입력의 최대값이 20억이여서 최악의 경우 최대 20억의 실행이 발생할 수있다.

그러므로 이진탐색을 사용하여야 한다.

 

아래는 나의 코드이다.

# 떡의 개수(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)

 

아래는 예시코드이다.

import sys
N,M=map(int,sys.stdin.readline().split())
ricecakeList=list(map(int,sys.stdin.readline().split()))
ricecakeList.sort()

def search(ricecakeList,mine):
    low=min(ricecakeList)
    high= max(ricecakeList)
    result = high
    while low<high:
        mid = (low + high) // 2
        cut_result = 0
        for i in ricecakeList:
            if mid < i:
                cut_result+=(i-mid)

        if cut_result == mine:
            return mid

        elif cut_result < mine:
            high=mid-1

        else:           #cut_result > mine:
            low=mid+1
            # if mid < result:  조건문이 필요없다. 조금씩 자를 떡을 늘려가기에 마지막에 자르는 떡이 가장 작다.
            result = mid

    return result

print(search(ricecakeList,M))