이진 탐색 - 떡볶이 떡 만들기

떡볶이 떡 만들기 (Python)

📝 문제 설명

떡볶이 떡의 길이가 일정하지 않습니다.

대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰줍니다.
절단기에 높이(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

---

💡 문제 해결 접근

1. h 의 범위가 0에서 10억 이여서 선형 탐색보단 이진 탐색 알고리즘을 사용하여 값을 찾는 범위를 빠르게 줄인다.
   • h 값을 탐색 하기 위해 시작점 start = 0 과 끝점 end = max(array) 활용함
   • h 값은 시작점과 끝점의 중간값 mid = (start - end) // 2 로 설정하여 중간값(절단 높이를 중간으로)부터 탐색
2. 떡을 중간값으로 절단 했을때 떡의 남은 길이의 합을 target 변수로 초기화 한다.
   • 떡의 남은 길이는 절단기로 자를 수 있는 떡의 길이만 잘라서 합한다.
   • target = sum([i - m for i in array if i > m])
3. 떡을 중간값으로 절단 했을때 손님이 주문한 길이(m)가 떡을 중간값으로 길이로 절단한 후 남은 떡의 길이(target)가 m 보다 커야 한다.
   • 떡의 남은 길이가 m 보다 작으면 위에서 설정한 중간값을 왼쪽 방향으로 이동함
   • 떡의 남은 길이가 m 보다 크거나 같으면 위에서 설정한 중간값을 오른쪽 방향으로 이동함
4. 떡의 남은 길이가 m 보다 크거나 같은 (target >= m) 이 되는 h 값을 저장한다.
5. 이진 탐색 알고리즘 방식으로 target 값에 따라서 중간값을 이동하면서 h 의 최댓값을 구한다.

def solution():
    n, m = 4, 6
    array = [19, 15, 10, 17]

    start = 0
    end = max(array)
    result = 0
    while start <= end:
        mid = (start + end) // 2
        target = sum([i - mid for i in array if i > mid])

        if target >= m:
            result = mid
            start = mid + 1
        else:
            end = mid - 1
    return result
solution()

---

🏆 정답 코드

def 모범답안():
    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
            start = mid + 1
    return result

---

🔥 느낀 점

• 절단기의 높이(h) 의 최댓값을 구하는 문제이기 때문에 h 를 이진 탐색의 mid 중간값으로 치환하여 생각해야한다.
• 최댓값이란 말은 target >= m, m이 커질 수 있는 조건 마다 result = mid 로 저장하여 최댓값이 됐을 때 while 문을 탈출하고 result 값을 리턴한다.
  • mid 값이 방향이 오른쪽 방향으로 가야하면서 start 와 end 가 겹칠 때 최댓값임
  • 범위를 좁혀나가면서 start 와 end가 겹치거나 엇갈리는 시점에 종료되기 때문에 중간값이 커지는 방향인
    if target >= m: result = mid 구문에 result 값을 저장하면서 갱신해줘야함