[이코테] 이진 탐색 - 떡볶이 떡 만들기 (Java)

문제

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

 

 

풀이

• 문제에서 구해야 하는 값은 손님이 요청한 총 길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값이다.
  • 절단기의 높이(H)가 클 수록 손님이 가질 수 있는 떡의 길이가 작아진다.
  • 그렇기 때문에 되도록 손님이 요청한 만큼의 떡만 줄 수 있도록 절단기의 높이를 조건에 부합하는 최댓값으로 설정해야 한다.
• 이를 위해서 절단기의 높이를 차근차근 바꾸며 손님이 요청하는 조건에 부합하는지 여부를 체크해야 한다.
• 절단기의 최대 높이는 주어진 떡 길이 중 최댓값이다. (=가장 긴 떡의 길이와 절단기 길이가 일치해 떡이 하나도 잘리지 않는 경우)
• 그러나, 절단기의 높이는 0~1,000,000,000 수까지 설정할 수 있기 때문에 이를 for(int i = 0; i <= 1000000000; i++) {} 과 같이 범위에 속하는 수를 차례대로 접근하면서 조건에 부합하는 값을 탐색하려 하면 시간이 초과한다.
• 위와 같이 탐색 대상 데이터의 개수가 1,000만 개를 넘어가거나 탐색 범위의 크기가 1,000억 이상이라면 이진 탐색 알고리즘을 사용해 탐색 시간을 줄일 수 있다.
• 이진 탐색을 사용해 범위를 절반씩 줄여가면서 '주어진 조건을 만족하는 절단기 높이의 최댓값' 을 탐색한다.
  • [이진 탐색 첫번째] 시작점 : 0 / 끝점 : 19 / 중간점 : 9
  • 절단기 높이가 9 일 때 떡이 얼마나 잘리며, 잘린 떡이 손님이 요청한 길이(M)에 부합하는가?
  • 잘린 떡의 총 길이가 25로, 손님이 요청한 길이 6에 비해 크다.
  • 절단기의 높이를 늘려서 다시 자른다.
• [0~가장 긴 떡의 길이] 범위 값에 이진탐색으로 접근(mid)하면서 해당 값을 절단기 높이로 하고 잘랐을 때 N개의 떡에서 얼만큼의 떡을 잘라낼 수 있는지(cutting) 매번 체크한다.
  • 잘라낸 떡이 M과 일치하는 경우
    • 현재 절단기 높이(mid) 반환 (이진 탐색 성공 시 반환값)
  • 잘라낸 떡이 M보다 작을 경우
    • 절단기 길이가 너무 커서 떡이 조금만 잘린다는 뜻이므로 절단기 길이를 줄이고 다시 자른다.
  • 잘라낸 떡이 M보다 클 경우
    • 손님이 요청한 길이(M)의 떡을 줄 수 있으나, 최대한 M 값에 가깝게 맞추기 위해 절단기 길이를 늘려서 다시 자른다. 
    • 다만, 끝내 M길이와 정확히 일치하도록 떡을 자를 수 없는 경우(=자투리 떡을 덤으로 주게되는 경우)를 산정해서 차선책으로써의 현 높이를 따로 변수에 저장해둔다. (이진 탐색 실패 시 반환값)

 

코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();   // 떡의 개수
        int m = sc.nextInt();   // 요청한 떡의 길이

        int[] array = new int[n];
        for (int i = 0; i < n; i++)
            array[i] = sc.nextInt();

        Arrays.sort(array);

        // 시작점 : 0, 끝점 : 가장 긴 떡의 길이 (오름차순 정렬한 배열의 마지막 원소)
        int result = binarySearch(array, m, 0, array[array.length - 1]);
        System.out.println(result);
    }

    private static int binarySearch(int[] array, int m, int start, int end) {
        int max = 0;

        while (start <= end) {
            int mid = (start + end) / 2;

            // 떡 자르기 (절단기 길이보다 짧은 떡은 0처리)
            int cutting = 0;
            for (int i : array) {
                cutting += Math.max((i - mid), 0);
            }

            if (cutting == m) {             // 자른 떡이 손님이 요청한 길이와 일치하는 최선책
                return mid;
            } else if (cutting < m) {       // 자른 떡이 손님이 요청한 길이보다 작음 -> 절단기 길이 줄이기
                end = mid - 1;
            } else {                        // 자른 떡이 손님이 요청한 길이보다 큼 -> 절단기 길이 늘리기 (최대한 요청 길이에 맞추도록)
                start = mid + 1;
                max = mid;
            }
        }

        // 손님이 요청한 길이에 딱 맞게 자르진 못하고 자투리 떡을 주게 되는 차선책
        return max;
    }
}