[알고리즘 PS] 백준 1654번 랜선 자르기 자바 문제풀이

문제

해당 포스팅은 백준의 1654번 랜선 자르기 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

문제 접근

문제에서 원하는 내용을 한 문장으로 말 하자면 다음과 같다.

K개의 랜선을 N개로 나누어 자를 때, 각 랜선의 길이가 최대가 되는 길이를 출력하라.

 

그럼 우선, 아무런 생각하지 말고 K개의 랜선을 N개로 나누어서 자를 때 최대의 길이를 구해보자.

 

어떠한 알고리즘이 생각나지 않아도 좋다.

아니 생각하지 말고 한 번 짜보자.

public static void main(String[] args) {
  int k = 4;
  int n = 11;

  int[] arr = {802, 743, 457, 539};
  Arrays.sort(arr);

  int quotient = 1;
  int answer = 1;

  while(quotient++ < arr[arr.length-1]) {
    int count = 0;
    for(int value : arr) {
      count += value / quotient;
    }

    if(n == count) { // n과 같으면서 나누어 떨어지는 최대값
      answer = quotient;
    }
  }
  System.out.println(answer); // 200
}

그럼 우리가 찾는 200이라는 수가 찾아지게 된다.

 

그럼 이게 답일까?

 

우선 논리에 대한 검증부터 해보자.

 

몫을 1 ~ 입력 배열의 최대값 까지 1씩 증가하며 나누었을 때, 우리가 원하는 n개의 랜선이 될 최대 값을 구하는 로직이다.

 

사실상 로직에는 문제가 없어 보인다.

 

로직은 통과했다. 하지만?

그럼 이제 가장 중요한 시간 복잡도를 생각해보자.

 

입력 k는 1 ~ 10,000 사이의 값이다. 그리고 N은 1 ~ 1,000,000 이하의 정수라고 한다.

 

그리고 랜선의 길이는 2^31 즉 21억 cm의 길이가 된다고 한다.

최악의 경우 21억번 반복을 돌아야 하므로 시간복잡도에서 실패

그럼 어떻게 해야할까?

 

지금까지 보면 어쩔 수 없이 1부터 21억의 길이를 탐색해야 할 것 같다.

하지만 조금 생각을 해본다면 1부터 21억 까지의 탐색을 술먹으며 자주 했던 업다운 게임 방식으로 줄일 수 있지 않을까?

 

맞다.

이 업다운 게임 자체는 이분 탐색으로 최적화 할 수 있으므로 이 문제도 이분 탐색 알고리즘을 사용하면 된다.

 

해결법

앞서 말 했듯, 입력으로 들어오는 배열 arr 의 원소를 나눈 몫들의 합이 바로 랜선의 갯수가 된다.

 

그럼 우리가 만드는 알고리즘은 arr 의 원소를 x로 나눴을 때, 몫들의 합이 n이 되는 x를 찾기 위한 과정이 될 것이고, 이 후보들을 이분 탐색하면 될 것 같다.

 

x의 후보

우리는 이 x의 범위는 1에서 배열 항목의 최대값인 802 까지가 된다.

 

이들을 반씩 줄여가며 혹은 늘려가며 이분 탐색을 시도하는데, 늘리고 줄이고를 어떻게 결정할까?

 

길이 x로 자른 랜선들의 갯수가 n보다 크거나 작거나로 나눌 수 있지 않을까?

 

• 길이 x로 자른 랜선들의 갯수가 n보다 클 때 : x로 잘랐더니 랜선이 더 많아졌다? => x보다 더 큰 길이로 잘라야 한다.
• 길이 x로 자른 랜선들의 갯수가 n보다 작을 때 : x로 잘랐더니 랜선이 더 적어졌다? => x보다 더 작은 길이로 잘라야 한다.

이 조건을 통해서 이분 탐색의 start와 end를 매 반복마다 재정의 해주면 된다.

정답 코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] kn = br.readLine().split(" ");
        int k = Integer.parseInt(kn[0]);
        int n = Integer.parseInt(kn[1]);
        long[] arr = new long[k];

        long max = 0;

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

        long start = 1;
        long end = max;
        long answer = 0;

        while(start <= end) {
            int count = 0;
            long mid = start + (end - start) / 2; // 나눌 값
            for(int i = 0; i < arr.length; i++) {
                count += arr[i] / mid;
            }

            if(count >= n) {
                answer = Math.max(answer, mid);
                start = mid + 1;
            }else {
                end = mid - 1;
            }
        }


        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
    }
}

---

문제 회고

이분 탐색 알고리즘으로 풀었던 첫 문제이다.
이론에서 이분 탐색은 지정된 리스트 내에서 분할 정복을 한다고 이해했는데, 틀에 박혀있어서 계속 입력으로 들어온 arr 이라는 리스트 내에서만 생각을 하게 되었다.
arr 리스트 내에서 어떻게 mid 값을 찾을지를 고민했는데, 사실은 이분 탐색을 해야할 리스트 자체가 달랐다.
이분 탐색을 해야할 리스트는 1 ~ arr의 최대값 까지 나누려 하는 값의 리스트 였었다.
확실히 알고리즘 PS는 많은 문제를 풀어봐야 할 것 같다.

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.