[백준] 1654번 랜선 자르기(Java)

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

1654번: 랜선 자르기

 

처음에는 주어진 랜선의 길이를 모두 더하고 필요한 개수로 나눈 후 1씩 감소하면서 필요한 개수 이상의 랜선이 나오게 되면 반복문을 나와 출력하도록 코드를 작성하였다.

 

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

public class Main {
    static int stoi(String s) {
        return Integer.parseInt(s);
    }

    static int N;
    static int M;

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

        N = stoi(st.nextToken());
        M = stoi(st.nextToken());

        int[] arr = new int[N];
        long sum = 0;

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i] = stoi(st.nextToken());
            sum += arr[i];
        }

        long length = sum / M;
        while(true) {
            long num = 0;
            for (int i = 0; i < N; i++) {
                num += arr[i]/length;
                if(num >= M) break;
            }
            if(num >= M) break;
            length--;
        }

        System.out.println(length);
    }
}

 

시간초과가 발생하였고 해당 문제의 알고리즘 분류가 이진 탐색이어서 공부해보았다.

 

이진 탐색(Binary Search)

앞에서는 문제 조건을 충족하는 길이를 찾기 위해 i--를 해주었다.

1씩 빼면서 답을 찾는 경우 속도가 느리기 때문에 이진 탐색을 사용하면 원하는 값을 더 빠르게 찾을 수 있다.

 

• 오름차순 혹은 내림차순으로 정렬된 배열에 적용 가능한 탐색 기법
• 시작점과 끝점 사이의 중앙값이 탐색값보다 작은 경우
  • 끝점을 중앙값으로 업데이트한다.
• 시작점과 끝점 사이의 중앙값이 탐색값보다 큰 경우
  • 시작점을 중앙값으로 업데이트한다.

 

lower bound, upper bound?

• 오름차순으로 정렬된 배열에서 탐색값이 여러 개인 경우, 
• lower bound: 가장 앞에 있는 탐색값
• upper bound: 탐색값 다음 위치의 값

 

위의 문제에서는 가능한 길이의 최대값을 구해야 하기 때문에 upper bound를 사용해야 한다.

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

public class Main {
    static int stoi(String s) {
        return Integer.parseInt(s);
    }

    static int N;
    static int M;
    static int[] arr;
    static long min = 1;

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

        N = stoi(st.nextToken());
        M = stoi(st.nextToken());

        arr = new int[N];
        long max = 0;

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i] = stoi(st.nextToken());
            if(max < arr[i]) max = arr[i];
        }

        binarySearch(max+1);

        System.out.println(min-1);
    }

    public static void binarySearch(long max) {
        if(min >= max) return;
        long mid = (min + max) / 2;
        long count = 0;
        for (int i = 0; i < N; i++) {
            count += arr[i] / mid;
        }

        if(count < M) {
            binarySearch(mid);
        }
        else {
            min = mid+1;
            binarySearch(max);
        }
    }
}

 

max값에 +1을 해줘야 한다.

 

 

참고

https://charles098.tistory.com/133

[ 알고리즘 ] 이분탐색(Binary Search), upper_bound, lower_bound (C++)

https://st-lab.tistory.com/269

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