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

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

1654번: 랜선 자르기

 

---

• 문제

 

 

---

• 문제 풀이

백준 1654번 랜선 자르기는 실버 2 난이도의 이분 탐색 및 매개변수 탐색 문제이다.

 

이 문제에서는 랜선 K개와 랜선의 길이, 그리고 필요한 랜선의 개수 N이 주어진다. 이때, N개를 만들 수 있는 랜선의 최대 길이를 구하면 된다. 

 

이 문제는 이분 탐색을 이용해서 풀 수 있다. 만약 이분 탐색에 대해 더 알고 싶으면 밑에 있는 링크를 참고하면 되겠다.

 

[알고리즘] 이분 탐색 (Binary Search)

 

우선 이미 가지고 있는 랜선의 길이들을 배열에 입력받고 랜선의 최대 길이를 int형 변수 high에 저장한다. 이 이유는 만약에 이 high 길이만큼 랜선들을 자르고 N개 이상의 랜선을 만들 수 있으면 이 길이가 정답이 되기 때문이다. 

 

랜선을 h 길이만큼 잘랐을 때 나오는 랜선의 개수를 구하는 함수는 다음과 같이 구현할 수 있다. 

 

// 특정 랜선 길이로 만들 수 있는 랜선 개수 계산
static int f(long h) {
    int sum = 0;
    for (int i = 0; i < k; i++) {
        sum += arr[i] / h;
    }
    return sum;
}

 

즉, 배열에 저장해 놓은 모든 랜선의 길이를 h로 나눈 값들의 합이 바로 h로 잘랐을 때 나오는 랜선의 개수가 된다. 이제 이 h를 구하면 되는데 이 h는 이분 탐색을 이용해서 구하면 된다.

 

우선 h의 탐색 범위를 살펴보겠다. 랜선을 자를 때 가장 짧은 랜선의 길이는 바로 1cm, 즉 1이 된다. 그리고 최대 길이는 이전에 따로 저장을 해놓았던 high이다. 이 1을 low라고 부르도록 하겠다.

 

이제 랜선의 길이의 탐색 범위는 low부터 high가 된다. 이 탐색 범위에서 이 길이만큼 랜선을 잘랐을 때 N개 이상의 랜선이 나오는 h값을 찾으면 된다. h값을 찾는 건 다음과 같이 할 수 있다.

 

// 이분 탐색
while (low < high - 1) {
    long mid = (low + high) / 2;
    if (f(mid) >= n) {
        low = mid;
    } else {
        high = mid;
    }
}

 

우선 low가 high - 1보다 작을 때 계속 loop을 돌려준다. 그리고 이분 탐색은 중간값을 비교해서 탐색 범위를 줄이는 알고리즘이다. 따라서, low와 high의 중간값 mid를 구해주고 f(mid)를 해준다. 전에서 설명했듯이 이 함수 f는 길이 h로 잘랐을 때 나오는 랜선의 개수를 반환한다. 

 

따라서, f(mid)가 N보다 크거나 같으면 탐색 범위를 mid에서 high로 바꿔준다. 왜냐면 중간값에서도 N개 이상의 랜선이 나오기 때문에 mid보다 작은 값들을 살펴볼 필요가 없다. 반대로, f(mid)가 N보다 작으면 탐색 범위를 low에서 mid로 바꿔주고 탐색을 계속한다.

 

자세한 코드는 아래에 있는 코드를 참고하면 되겠다.

 

---

• 코드

 

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

public class Main {
    static int[] arr;
    static int k;
    static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 입력 받기
        k = Integer.parseInt(st.nextToken());  // 이미 가지고 있는 랜선 개수
        n = Integer.parseInt(st.nextToken());  // 필요한 랜선 개수

        arr = new int[k];

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

        // 초기 설정을 통해 이분 탐색 범위 지정
        if (f(high) >= n) {
            System.out.println(high);
            return;
        }

        // 이분 탐색
        while (low < high - 1) {
            long mid = (low + high) / 2;
            if (f(mid) >= n) {
                low = mid;
            } else {
                high = mid;
            }
        }
        System.out.println(low);
    }

    // 특정 랜선 길이로 만들 수 있는 랜선 개수 계산
    static int f(long h) {
        int sum = 0;
        for (int i = 0; i < k; i++) {
            sum += arr[i] / h;
        }
        return sum;
    }
}