[백준]1654 - 랜선 자르기 문제 풀이(Java,자바)

들어가며

여러 가지 푸는 방법이 있겠지만, 이 글에선 정렬과 이분 탐색을 사용한다.

풀이법

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;

public class 백준1654_랜선자르기 {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] s = reader.readLine().split(" ");
        int k = Integer.parseInt(s[0]);
        int n = Integer.parseInt(s[1]);

        ArrayList<Integer> sticks = new ArrayList<>();
        for (int i = 0 ; i < k; i++){
            sticks.add(Integer.parseInt(reader.readLine()));
        }
        sticks.sort(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return Integer.compare(o1,o2);
            }
        });

        findBest(sticks, n);
    }
    public static long calculateSticks(ArrayList<Integer> lists, long length){
        long result = 0;
        for (var i : lists){
            result += i / length;
        }
        return result;
    }

    public static void findBest(ArrayList<Integer> sticks,int n){
        long start = 1;
        long end = sticks.get(sticks.size()-1);
        long stickLength = 0;
        while (start <= end){
            long mid = (start + end) / 2;
            long stickCount = calculateSticks(sticks, mid);
            if (stickCount < n){
                end = mid -1;
            } else {
                start = mid+1;
                stickLength = mid;
            }
        }
        System.out.println(stickLength);
    }
}

설명

먼저, K 개의 랜선 길이들을 ArrayList에 저장한 뒤에 정렬을 하여 가장 긴 길이의 랜선을 찾는다.

이 랜선의 길이를 기준으로 만들 수 있는 랜선의 개수를 계산한다.

1 <= 랜선 길이 <= 가진 기존 랜선 길이 중 가장 긴 길이

 

위 조건을 만족해야 문제에서 원하는 결과를 구할 수 있다.

왜냐하면 가장 긴 길이에서 가장 많이 랜선을 뽑아낼 수 있기 때문이다.

 

그러면 어떻게 길이를 찾을까??

가장 쉬운 방법 중 하나는 이분 탐색을 사용하는 것이다.

먼저, 가진 기존 랜선 길이 중 가장 긴 길이의 반부터 몇 개의 랜선을 만들 수 있는지 확인한다.

(calculateSticks() 메소드는 몇 개의 랜선을 만들 수 있는지 계산하는 메소드이다)

 

만약 만들 수 있는 랜선의 개수가 n 보다 작으면, 길이를 줄여 다시 계산한다.

만약 만들 수 있는 랜선의 개수가 n 보다 크거나 같으면, 최대값을 찾기 위해 길이를 올려 다시 계산한다.

 

위 과정을 무한으로 반복하다보면 결국 n 개 이상을 만드는 최대 길이를 구할 수 있게 된다.

 

참고

여기선 double을 쓰면 안된다. double은 기본적으로 큰 수에 대해서 지수로 표현하기 때문에 문제가 원하는 정수를 표현하지 않는다.

이를 위해 long을 써야 된다.