(JAVA) 백준 문제 풀이 - 이분 탐색 단계 - 1654번 랜선 자르기 (실버 2)

이번 문제는 이분 탐색 기법을 활용하여 랜선의 갯수와 길이가 주어질 떄, 만들어야 할 랜선의 갯수를 충족하는 최대 길이 값을 구하는 문제이다.

처음 문제를 보았을 때는 어떻게 풀어야 할지 잘 생각이 나지 않았는데 문제 설명을 보면 파라메트릭 서치(Parametric Search)라는 말이 나와 검색을 해보고 풀 수 있었다.

그럼 파라메트릭 서치가 어떤 것이고 어떻게 문제를 풀었는지 다시 한번 복기해본다.

---

파라메트릭 서치(Parameteric Search)란?

파라메트릭 서치는 주어진 문제가 최적화 문제(최대, 최소값을 구하는 문제) 일 때 주로 사용한다.

이진 탐색과의 비슷하지만 차이가 있다면 이진 탐색이 결정 문제(특정 값이 존재하는지 여부)를 해결하는데 사용된다면 파라메트릭 서치는 최적화 문제의 답을 찾는데 사용된다는 것이 다르다.

예를 들어, 이전에 풀었던 수찾기의 경우, 주어진 배열에서 특정 값을 빠르게 찾아내는 로직이다.

하지만 이번 문제에서는 특정 값을 찾는 것이 아닌 특정 환경에서의 최대값을 찾아내는 문제이다.

특정 값이 아닌 범위를 찾아내는 알고리즘이기 때문에 최적화라고 말하는 것이다. (좀 더 쉽게 말하면, 특정 값을 구하는 것이 아니라, 특정값이 어떤 조건을 만족하는지만 확인한다고 생각하면 될것이다.)

일반적인 파라메트릭 서치의 코드는 다음과 같다.

long parametricSearch(int[] arr, int target) {
    long left = 0, right = Integer.MAX_VALUE;
    while (left <= right) {
        long mid = (left + right) / 2;
        if (isPossible(arr, target, mid)) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return right; // 최적의 답
}

boolean isPossible(int[] arr, int target, long mid) {
    // mid를 기준으로 가능한지 여부를 판단하는 함수
    // 예: mid를 기준으로 나눌 수 있는 랜선의 개수가 target 이상이면 true 반환
}

결론적으로, 어떤 값을 찾아내는 것은 같지만 어떤 값이 주어진 환경에 맞는지 판단하는 여부가 추가되는 것이 파라메트릭 서치라고 생각하면 되겠다.

---

문제에는 어떻게 적용해야 하는가?

그럼 이제 중요한 것은 이 로직을 지금 문제에 어떻게 적용해야 할까 고민해보자.

이분 탐색 기법은 전 글에서 설명한 것처럼 Mid 값을 만들고 미드 값에서 시작, 종료 값 까지의 범위를 탐색하는 방법이다.

그럼 이번 문제에서 이분 탐색을 적용하지 못하는 이유는 무엇일까?

예를 들어 중간값이 198이 들어왔다고 가정해보자.

198은 총 11개를 만들 수 있고, 다른 랜선 4가지의 길이를 넘지 않으니 조건에 충족한다.

그러나 실제로는 199, 200도 조건을 충족하므로 우리는 최대값 200을 구하기 위해서는 이분 탐색 기법으로는 답을 구할 수 없는 것이다.

그럼 파라메트릭 서치를 이용하면 어떻게 구현할 수 있을까?

이 문제에서의 핵심은 주어진 갯수를 만들지 못하는 첫 숫자, 즉 상한선을 찾는 것이다.

우리가 찾아야 하는 값은 최대 값만 알면 되므로 최대값을 넘어서는 숫자를 찾아 -1만 해주면 최대값이 되는 것이다.

그렇다면 우리는 총 랜선 길이를 카운트할 변수를 만들어 배열을 순회하면서 배열값 / Mid값을 한 후, 주어진 랜선 갯수가 안될때의 값에서 -1을 해주면 되는 것이다.

그렇다면 Mid 값은 어떻게 구해 줄 것인가?

이분 탐색처럼 최소 길이와 최대길이를 더한 후 2로 나누어주면 된다.

다만 최대값이 미지수 이므로 초기 최대 값을 가장 긴 로프 길이로 해준다.

그럼 직접 코드를 보면서 살펴보자.

---

import java.io.*;
import java.util.*;

class Main{
    public static int n, k;
    public static int[] arr;
    public static String[] str;
    public static long max, min, mid;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        str = br.readLine().split(" ");
        k = Integer.parseInt(str[0]);
        n = Integer.parseInt(str[1]);
        arr = new int[k];

        max = Long.MIN_VALUE;
        min = 0;

        for (int i = 0; i < k; i++) {
            arr[i] = Integer.parseInt(br.readLine());
            max = Math.max(arr[i], max);
        }
        max++;

        while (min < max) {
            mid = (min + max) / 2;

            long cnt = 0;

            for (int i = 0; i < k; i++) {
                cnt += arr[i] / mid;
            }

            if (cnt < n) {
                max = mid;
            } else {
                min = mid + 1;
            }
        }

        System.out.println(min - 1);
    }
}

코드를 살펴보면 max와 min을 변수 선언 하고 초기 값으로 max에는 가장 긴 랜선의 값과 min 에는 0을 설정해 두었다.

한가지 살펴볼것은 max++를 해준 것인데, 이것은 만약 가장 긴 로프값이 1이라면 첫 Mid 값이 0이 되기 때문에 0으로 나누게 되면 에러 발생을 방지하기 위해 초기 값에 ++를 해준것이다.

 

그 이후 while문으로 min이 max 보다 커질때 까지 계속 적으로 순회하며 배열의 각 랜선 길이를 mid로 나누어 모두 더해준다. 이렇게 되면 cnt에는 현재 mid 값으로 모든 로프를 나눈 갯수가 들어오게 되는데 이 값이 주어진 값 n을 넘어서면 최대값을 넘어선 것이므로 min을 max+1로 바꿔주어 while문을 탈출하게 한다.

 

그후 최종적으로 min값에서 1을 빼주면 가장 긴 랜선의 최대값을 얻을 수 있게 된다.

---

참고자료

https://st-lab.tistory.com/269

[백준] 1654번 : 랜선 자르기 - JAVA [자바]

https://marades.tistory.com/7