1654번: 랜선 자르기 - Baekjoon Online Judge

1654번: 랜선 자르기 - Baekjoon Online Judge

https://www.acmicpc.net/problem/1654

랜선 자르기 문제는 이분 탐색을 이용하여 범위 내에서 원하는 개수의 랜선을 만들되 그 길이는 최대값이 되도록 하는 문제이다. 원하는 값을 찾기에는 너무 많은 값을 하나씩 대입해야 하기 때문에 이분 탐색을 이용하여 가능한 후보군을 줄임으로써 시간내에 원하는 값을 찾을 수 있다.

이분 탐색 문제를 푼다고 했을 때 구현에서 차이가 나는 부분은 어떤 기준으로 중앙값을 옮겨줄 것인가이다. 이 문제의 경우 주어진 랜선을 적절하게 잘라서 원하는 개수를 맞춰주는 것이기 때문에 랜선의 길이가 중앙값 이동의 기준이 된다. 처음 중앙값은 0에서 int의 max값 사이에 있다는 것을 가정하고 그 중간값으로 계산을 시작했다. 중앙값을 구한 후, 주어진 랜선들을 이용하여 중앙값 길이의 랜선을 몇 개 만들수 있는지 카운팅을 해준다. 개수가 너무 많은 경우라면 중앙값을 더 큰쪽으로 이동시켜줘서 개수를 줄이고 길이는 늘려주는 쪽으로 탐색해주고, 만일 개수가 부족하다면 중앙값을 더 작은쪽으로 이동시켜서 개수를 늘리고 길이는 줄이는 방향으로 탐색을 이어나간다. 또한 우리는 개수만 만족한다고 해서 답을 찾았다고 할 수 없고 개수를 만족하는 랜선 길이 중에서도 최대값을 찾아야 하기 때문에 개수를 만족하는 중앙값 중에서도 제일 큰 값을 답으로 저장해서 출력해야한다.

실제 문제에서는 어떻게 구현했는지 소스를 통해 살펴보자.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    private static int N;
    private static int K;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
 
        st = new StringTokenizer(br.readLine().trim());
 
        K = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
 
        long[] L = new long[K];
        for (int i = 0; i < K; i++) {
            L[i] = Long.parseLong(br.readLine().trim());
        }
        long l = 0;
        long r = Integer.MAX_VALUE;
        long max = 0;
        long m = 0;
        int cnt = 0;
 
        while (l <= r) {
            m = (l + r) / 2;
            cnt = 0;
            for (int i = 0; i < K; i++) {
                cnt += (L[i] / m);
            }
            if (cnt >= N) {
                l = m + 1;
                if (max < m)
                    max = m;
            } else {
                r = m - 1;
            }
        }
        System.out.println(max);
    }
}