[Binary Search] 떡볶이 떡 만들기

떡볶이 떡 만들기

난이도 : ⭐⭐

오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했다. 오늘은 떡볶이 떡을 만드는 날이다. 동빈이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않다. 대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다.
절단기에 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다.
예를 들어 높이가 19, 14, 10, 17cm인 떡이 나란히 있고 절단기 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15, 14, 10, 15cm가 될 것이다. 잘린 떡의 길이는 차례대로 4, 0, 0, 2cm이다. 손님은 6cm만큼의 길이를 가져간다.
손님이 왔을 때 요청한 총 길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최대값을 구하는 프로그램을 작성하시오.

입력 조건

• 첫째 줄에 떡의 개수 N과 요청한 떡의 길이 M이 주어진다. (1 <= N <= 1,000,000, 1 <= M <=2,000,000,000)
• 둘째 줄에는 떡의 개별 높이가 주어진다. 떡 높이의 총합은 항상 M 이상이므로, 손님이 필요한 양만큼 떡을 사갈 수 있다. 높이가 10억보다 작거나 같은 양의 정수 또는 0이다.

출력 조건

• 적어도 M만큼의 떡을 집에 가져가기 위해 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

입력 예시
4 6
19 15 10 17

출력 예시
15

나의 풀이 : 틀려서 추후에 수정 필요

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

# 10 15 17 19
def binary_search(array, target, start, end):
    while start <= end:
        count = 0
        mid = (start + end) // 2

        for x in lenArr:
            if mid < x:
                count += (x - mid)

        if target == count:
            return mid
        # 떡의 양이 부족한 경우 : 더 많이 잘라야 한다. 왼쪽으로!
        elif target > count:
            end = mid - 1
        else:
            start = mid + 1
    return None

print(binary_search(lenArr, m, 0, max(lenArr)))

문제 해설

전형적인 이진 탐색 문제이자, 파라메트릭 서치(Parametric Search) 유형의 문제이다. 마라메트릭 서치는 최적화 문제를 결정 문제로 바꾸어 해결해가는 기법이다. 원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제에 주로 파라메트릭 서치를 사용한다. 예를 들어 범위 내에서 조건을 만족하는 가장 큰 값을 찾으라는 최적화 문제라면 이진 탐색으로 결정 문제를 해결해가면서 범위를 좁혀갈 수 있다. 코딩 테스트나 프로그래밍 대회에서는 보통 파라메트릭 서치 유형은 이진 탐색을 이용하여 해결한다.
이 문제의 풀이 아이디어는 적절한 높이를 찾을 때까지 절단기의 높이 H를 반복해서 조정하는 것이다. 그래서 ‘현재 이 높이로 자르면 조건을 만족할 수 있는가?’를 확인한 뒤에 조건의 만족여부에 따라서 탐색 범위를 좁혀서 해결할 수 있다. 범위를 좁힐 때는 이진 탐색의 원리는 이용하여 절반씩 탐색 범위를 좁혀 나간다.
절단기의 높이(탐색 범위)는 1부터 10억까지의 정수 중 하나인데, 이처럼 큰 수를 보면 당연하듯 가장 먼저 이진탐색을 떠올려야 한다. 만약 순차 탐색으로 했을 경우 시간초과!!
아래에서 절단기의 적절한 높이 H를 정하는 과정을 살펴보자.

step 1 시작점은 0, 끝점은 가장 긴 떡의 길이(19)로 설정한다. 0과 19 사이의 중간점 9를 절단기 높이 H로 설정하면 얻을 수 있는 떡의 합은 (10 + 6 + 1 + 8) = 25 이다. 필요한 떡의 길이가 6보다 크기 때문에 시작점을 증가시킨다.

step 2 시작점을 10으로 옮긴다. 끝점은 여전히 19이므로 중간점은 14이다. 절단기 높이를 14로 설정하면 얻을 수 있는 떡의 합이 (5 + 1 + 3) = 9이다. 여전히 필요한 떡의 길이인 6보다 크기 때문에 시작점을 증가시킨다.

step 3 현재 시작점은 15, 끝점은 19, 중간점이 17이므로 얻을 수 있는 떡의 합은 2이다. 필요한 떡의 길이인 6보다 작기 때문에 끝점을 감소시킨다.

step 4 현재 시작은 15, 끝점은 16, 중간점이 15이므로 얻을 수 있는 떡의 합은 (4 + 2) = 6이다. 필요한 떡의 길이인 6과 동일하다.

답안 예시

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

---

🐢 현재 공부하고 있는 이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈 저자 의 책을 학습하며 기록 및 정리를 하기위한 내용들입니다. 🐢

감사합니다.😊

Algorithm 카테고리 내 다른 글 보러가기