떡볶이 떡 만들기

이 문제는 전형적인 이진 탐색 문제이자 파라메트릭 서치 유형의 문제이다. 파라메트릭 서치는 최적화 문제를 예/아니요로 답하는 문제인 결정 문제로 바꾸어 해결하는 기법이다.

이 문제 풀이는 절단기 높이를 반복해서 조정하는 것이다. 당연한 말이지만 절단기 높이는 0부터 가장 긴 떡의 길이 안에 있어야 한다. 

따라서 절단기의 범위인 0~가장 긴 떡의 길이를 고려하면 된다. start는 0이고 end는 가장 긴 떡의 길이로 두면 된다.

 

내 풀이

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

def search(ary, target, start, end):
    mid = (start + end) // 2
    sum = 0
    for i in range(n):
        t = ary[i] - mid
        if t > 0:
            sum += t
        
    if sum == target:
        return mid
    elif sum > target:
        return search(ary, target, mid + 1, end)
    else:
        return search(ary, target, start, mid-1)
    
print(search(ary, m, 0, ary[-1]-1))

나는 재귀적인 방식으로 풀어봤다. 예시에 적힌건 답이 나오긴 하지만 다른 예시에서는 정답이 나오지 않을 수 있을 것 같다. 왜냐하면 손님이 원하는 떡의 길이가 딱 맞아 떨어지지 않을 수도 있기 때문이다.

 

책 풀이

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

start = 0
end = max(ary)
result = 0

while (start <= end):
    total = 0
    mid = (start + end) // 2
    
    for i in range(n):
        if ary[i] - mid > 0:
            total += ary[i] - mid
        
    if m > total:
        end = mid - 1
    else:
        result = mid
        start = mid + 1

print(result)

책에서는 반복적 재귀 방법을 사용했다. 반복접 재귀를 사용하는 것이 더 간결하게 문제를 풀 수 있다.

이 코드를 안보고 풀어보면서 실수했던 점은 total을 while문 밖에 선언했었다. 그리고 total과 m을 비교하는 if문에서 부등호를 잘못했다.

m이 total보다 크면 떡을 짧게 자른거니까, 떡을 길게 자르기 위해서는 절단기의 높이를 짧게 해줘야해서 end를 mid-1로 바꿔줘야한다. 

반대로 m이 total보다 작으면 떡을 길게 자른거다. 일단은 떡이 길면 손님이 가져갈 수는 있으니까 result에 저장하고 start를 mid+1로 바꿔준다.