[이진 탐색] 문제 이름 : 떡볶이 떡 만들기 - 파라메트릭 서치

문제 설명

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

요청한 총 길이가 M일 때 적어도 M 만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

 

입력 조건)

떡의 개수 N (1 <= N <= 1,000,000)

요청한 떡의 길이 M (1 <= M <= 2,000,000,000)

떡의 개별 높이 : 10억보다 작거나 양의 정수 또는 0

 

사용 개념

이진 탐색

 

문제 해결 아이디어

이진탐색 문제이자, 파라메트릭 서치(Parametric Search) 유형의 문제임

→ 파라메트릭 서치는 최적화 문제를 결정 문제('예' or '아니오'로 답하는 문제)로 바꾸어 해결하는 기법

→ 원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제에 주로 파라메트릭 서치를 사용함

→ 범위 내에서 조건을 만족하는 가장 큰 값을 찾으라는 최적화 문제라면 이진 탐색으로 결정 문제를 해결하면서 범위를 좁혀갈 수 있음

 

해당 문제의 전체 적용 개념 : '적절한 절단기의 높이를 찾을 때까지 절단기의 높이 H를 반복해서 조정하는 것'

따라서 '현재 이 높이로 자르면 조건을 만족할 수 있는가?' 를 확인한 뒤 조건의 만족 여부('예' or '아니오')에 따라서 탐색 범위를 좁혀서 해결할 수 있음 → 이때 이진탐색의 원리를 이용해 절반씩 탐색 범위를 좁혀 나감

 

Q. 이진 탐색을 사용한 이유

탐색할 절단기의 높이는문제에서 주어진 떡의 개별 높이의 길이와 동일함

즉 1~10억까지의 정수 중 하나이므로, 이진탐색으로 수행해야 함

(만약 절단기의 높이 범위가 더 작은 수로 한정적이었다면 순차 탐색으로도 가능함)

 

코드

import java.util.Scanner;

public class Q2 {
    public static void main(String[] args) {
        Scanner kbd                = new Scanner(System.in);

        int numOfRiceCake            = kbd.nextInt();    // 떡의 개수 
        int wantedLengthOfRiceCake = kbd.nextInt();    // 요청한 떡의 길이 

        int[] arrOfRiceCake        = new int[numOfRiceCake];
        int maxLength                = 0;
        for(int i = 0; i < numOfRiceCake; i++) {
            arrOfRiceCake[i] = kbd.nextInt();

            if(arrOfRiceCake[i] > maxLength) {    // 주어진 떡 길이의 최대값 찾기 
                maxLength = arrOfRiceCake[i];    
            }
        }


        // 반복문 사용하여 이진탐색 구현
        int result                     = 0;    // 절단기 높이 최댓값 (구하는 값) 
        int minLength                 = 0;
        while(minLength <= maxLength) {
            int cuttedTotalLength     = 0;    // 절단된 떡의 길이 총합 
            int midLength             = (maxLength + minLength) / 2;    // 절단기 높이 값 

            for(int i = 0; i < numOfRiceCake; i++) {    // 절단 떡의 길이 총합 계산 
                if(arrOfRiceCake[i] > midLength) {
                    cuttedTotalLength += (arrOfRiceCake[i] - midLength);
                }
            }

            if(cuttedTotalLength >= wantedLengthOfRiceCake) {    // 자른 떡의 길이가 원하는 길이보다 크거나 같은 경우 (오른쪽 부분 탐색) - 더 긴 절단기 높이를 찾아야 함(높이의 최댓값을 찾기 위해서) 
                result                 = midLength;    // 요청한 떡의 길이 이상이어야 하는 조건은 만족하므로 저장해둠 
                minLength             = midLength + 1;
            }
            else if(cuttedTotalLength < wantedLengthOfRiceCake) {        // 자른 떡의 길이가 원하는 길이보다 작은 경우 (왼쪽 부분 탐색) - 더 짧은 절단기 높이를 찾아야 함 
                maxLength             = midLength - 1;
            }
        }

        System.out.println(result);    // 정답 출력 

    }

}

처음에 생각하지 못한 부분:
처음에 문제를 풀 때 이진탐색 대상이 되는 배열을 주어진 떡의 개별 높이로 설정했었다. 하지만 이렇게 설정을 하게 되면 절단기의 높이 값이 주어진 개별 높이 값과 다른 경우가 있을 수 있고, 그렇게 되면 주어진 떡의 개별 높이 이진 탐색 & 좁혀진 범위로 대상이 되는 배열을 다시 설정해 또다른 이진 탐색 수행해야 하는 문제점이 있다.
따라서 이진탐색 대상이 되는 배열을 0 ~ 떡의 개별 높이 길이의 최대값 으로 설정하면 편리하다.