[이진탐색] 떡볶이 떡 만들기

배씌 2024. 11. 26. 00:51

문제

절단기에 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다.

예를 들어 높이가 19, 14, 10, 17인 떡이 나란히 있고 절단기 높이를 15로 지정하면 자른 뒤 떡의 높이는 15, 14, 10, 15가 될 것이다. 잘린 떡의 길이는 차례대로 4, 0, 0, 2이다. 손님은 6만큼의 길이를 가져간다.

손님이 왔을 때 요청한 총 길이가 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 입력
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
// 떡 길이 입력
int[] cakes = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
    cakes[i] = Integer.parseInt(st.nextToken());
}

탐색의 시작점은 0, 끝점은 배열 내 떡의 최댓값으로 지정한다.

// 이진 탐색 시작점, 끝점
int start = 0;
int end = Arrays.stream(cakes).max().getAsInt();

이후 이진 탐색을 수행하면 되는데, 잘린 떡의 합을 구하면서 그 값이 M을 넘는지, 혹은 부족한지 비교하며 인덱스 범위를 조절해나간다. 문제에서 높이의 최댓값을 구하라 했으니, 최대한 덜 잘랐을 때의 인덱스 값이 정답이다.

이진 탐색은 재귀 방식과 반복문 방식으로 구현할 수 있는데, 이 문제와 같은 파라메트릭 서치 문제 유형은 재귀적으로 구현하지 않고 반복문을 이용해 구현하면 더 간결하게 문제를 풀 수 있다는 것을 기억하자.

// 이진 탐색 수행
int result = 0;
while(start <= end) {
    int total = 0;
    int mid = (start + end) / 2;
    for(int i : cakes) {
        if(i > mid)
            total += (i - mid);
    }
    // 떡의 양이 부족한 경우 더 많이 자르기(왼쪽 부분 탐색)
    if(total < M)
        end = mid - 1;
    // 떡의 양이 충분한 경우 덜 자르기(오른쪽 부분 탐색)
    else {
        result = mid;   // 최대한 덜 잘랐을 때가 정답이므로, 여기에서 result에 기록
        start = mid + 1;
    }
}