[백준] 떡볶이 떡 만들기

출처:: 

분류:: 이진탐색 , 파라메트릭 서치 

 

1. 문제 이해 및 해결과정

- 전형적인 이진 탐색 문제, 파라메트릭 서치 유형 - 파라메트릭 서치(Parametric Search) : 최적화 문제를 결정 문제로 바꾸어 해결하는 기법, 원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제에 사용 - 현재 문제에서 절단기의 높이는 최대 10억까지의 정수 -> 순차탐색은 시간초과, 큰 수를 보면 당연하단 듯이 이진탐색 떠올리자!! - 이진탐색으로 찾는 다면, 대략 31번 만에 경우의 수 모두 고려 가능 - 떡의 개수 N이 최대 100만개 이므로 , 최대 3000만번 정도의 연산으로 문제를 풀 수 있음 - 문제 제한 시간 2초이므로 최악의 경우 3000만번 정도 연산이 필요하면 2초 남짓 정답

 

2. 풀이방법

 1. 이진탐색

#떡볶이 떡 만들기
#
import sys
sys.stdin = open("input.txt","r")
n,m=map(int,input().split())
arr=list(map(int,input().split()))
arr.sort()
result=0
def cake(candi):
    sum=0
    for i in range(n):
        diff=arr[i]-candi
        if diff<0:
            diff=0
        sum+=diff
    return sum


def binary_search():
    global result
    s=0
    e=max(arr)
    while s<=e:
        mid=(s+e)//2
        target = cake(mid)
        if target>=m:
            s=mid+1
            result=mid
        else:
            e=mid-1

binary_search()
print(result)

3. 오답원인

 

4. 알게된 점