백준 1654 : 랜선 자르기 - Java

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

문제 분석

각각 길이가 다른 K개의 랜선을 잘라서, N개 이상의 같은 길이의 랜선으로 만들기

제한 조건과 시간복잡도 계산

• 제한 조건
  1. 시간제한 : 2초 ➡️ 2 * 10^8 번의 연산 가능 ( 2억번 )
  2. K : 10^4
  3. N : 10^6
  4. 랜선의 길이는 int 의 범위 내 자연수

• 시간복잡도 범위 : O(N log N) 이하
  • N log N <<  2 x 10^8  < N x K <  N^2
  • 10^6 x 19.93... <<  2 x 10^8  <  10^10  <  10^12

 

---

정답 설계

최대 길이는 K개의 랜선중 가장 작은 길이의 랜선

가능한 랜선의 길이는 [ 1 ~ 최대길이 ]로 정렬되어 있고 참, 거짓 판단이 가능하기 때문에 이진탐색으로 진행 가능

---

note.

note.1 : 최대길이 설정

처음에는 설정할 수 있는 "최대" 길이는 K개의 랜선 중 가장 작은 랜선의 길이라고 단정지었다. 하지만 "...N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이때 만들 수 있는 최대 랜선의 길이... " 라는 문제의 내용으로 인해 그 설정은 틀렸다는 사실을 알 수 있다.

 

만약 딱 하나의 랜선의 길이가 1이고 이 외의 다른 랜선들의 길이가 길 경우, 한개를 뺀 다른 랜선들만을 사용해 개수를 맞추고 길이는 더 길게 만들 수 있는 경우가 존재한다. 그럼으로 수정된 최대 길이는 ( K개의 랜선의 길이의 총합 / N )이다.

note.2 : 이진탐색의 반환값이 end인 이유

end를 반환값으로 하는 이유는 내가 구현한 코드의 탐색 방향 때문이다. 판단이 참일 경우 start를 올리는 방향으로 이진탐색이 진행된다. 따라서 마지막에 조건에 참인 값은 start가 아닌 start가 지나온 end이기 때문에 end를 반환한다.

note.3 : 최대길이 설정을 max로 하면 오답인 이유

"어차피 이진탐색인데 최대길이를 랜선들 중 가장 긴 길이로 설정해도 정상동작해야 하지 않나"라는 생각으로 구현해봤다. 길이가 Int 범위의 끝이라해도 log( 2^31 - 1 )의 시간복잡도를 갖기 때문이다.

 

하지만 오답이 발생했는데 이유는 내가 구현한  참, 거짓을 판단하는 함수의 시간복잡도가 O( 전체 길이의 합 / 탐색에 사용되는 길이 )의 시간복잡도를 갖기 때문이었다. 그래서 총 시간복잡도가 O( log( 2^31 - 1 ) x ( 전체 길이의 합 / 탐색에 사용되는 길이 ) ) 가 되면서 시간초과가 발생했다.

 

판단함수를 논리적으로 짜다가 생긴 문제이며, 리팩토링해서 O(K)로 시간복잡도를 낮췄다.

note.4 : 자료형

변수를 long이 아닌 int로 선언했을 때 오답인 이유는 start와 end를 int로 할 경우 start + end의 값은 int의 범위를 넘어갈 수 있기 때문이다. 그래서 start,mid,end를 모두 long으로 선언해야 한다.

---

제출코드

import java.util.Scanner;

class Main {

    public static void main(String args[]) throws Exception {

        Scanner sc = new Scanner(System.in);

        int k = sc.nextInt();
        int n = sc.nextInt();
        int max = 0;

        int[] arr = new int[k];

        for (int i = 0; i < k; i++) {
            arr[i] = sc.nextInt();
            max = Math.max(max, arr[i]);
        }

        long start = 1;
        long end = max;
        while (start <= end) {
            long mid = (start + end) / 2;
            if (isPossible(arr, mid, n)) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        System.out.println(end);
    }

    public static boolean isPossible(int[] arr, long targetLength, int targetCount) {
        long count = 0;
        for (int len : arr) {
            count += len / targetLength;
        }
        return count >= targetCount;
    }
}