자바(Java) 알고리즘 문제풀이 떡볶이 떡 만들기 [이코테 / 이분탐색]

 

 

 

---

 

 

 

문제 설명

오늘 동빈이는 여행 가신 부모님을 대신해 떡집 일을 하기로 했다. 오늘은 떡볶이 떡을 만드는 날이다. 동빈이네 떡볶이 떡은 재밌게도 길이가 일정하지 않다. 대신 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다.

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

예를 들어, 높이가 19, 14, 10, 17cm 인 떡이 나란히 있고 절단기 높이를 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 만큼의 떡을 집에 가져가기 위해 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

 

 

풀이 코드

백준의 랜선 자르기, 파닭파닭과 유사한 문제로, 파라메트릭 서치 유형의 문제이다.

원하는 조건을 만족하는 가장 알맞은 값을 찾아내는 문제에 주로 파라메트릭 서치를 사용하는데, 예를 들어 범위 내에서 조건을 만족하는 가장 큰 값을 찾으라는 최적화 문제라면 이진 탐색으로 결정 문제를 해결하면서 범위를 좁혀갈 수 있다.

 

이 문제는 앞서 언급한 두 문제를 풀어봤다면 어렵지 않게 해결할 수 있다. 다만 이런 유형의 문제는 입력 값이 굉장히 크기 때문에 int 를 사용해도 되는지, 불가능하다면 long 타입 정수형을 사용할 지에 대해 주의하면 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class 떡볶이_떡_만들기 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr);

        int answer = 0;
        int start = 0;
        int end = 1_000_000_000;

        while (start <= end) {
            int target = 0; // 임의의 절단기 높이 mid 로 잘린 떡 길이의 합
            int mid = (start + end) / 2;

                for (int i = 0; i < n; i++) {
                    if (arr[i] > mid) { // 떡 높이가 절단기 높이보다 낮아야 잘리니까
                    target += (arr[i] - mid);
                }
            }

            // 절단기 높이가 너무 낮음
            if (target == m) {
                answer = mid;
                break;

            } else if (target < m) {
                end = mid - 1;

            // 절단기 높이가 너무 높음
            } else  {
                start = mid + 1;
            }
        }

        System.out.println(answer);
    }
}