[알고리즘] 백준 1654 랜선 자르기 -이분탐색- 자바

www.acmicpc.net/problem/1654

1654번: 랜선 자르기

 

 

백준 이분탐색 단계별풀기 랜선 자르기를 풀어봤습니다.

이분탐색을 살짝 응용한 문제입니다. 각각의 랜선을 최대 몇 cm로 잘라야 해당 자른 cm와 같은 랜선이 N개 생기냐는 문제입니다.

주의할 점은 int 범위가 벗어나므로 long 형 사용하는 것과 이분탐색시 left값을 0이 아닌 1로 세팅해야 된다는 점 입니다.

 

풀이는 다음과 같습니다.

 

[Java]

 

import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int K = sc.nextInt();
        long N = sc.nextLong();
        long[] arr = new long[K];
        long max = 0;
        for (int i = 0; i < K; i++) {
            arr[i] = sc.nextLong();
            max = Math.max(max, arr[i]);
        }
        //이분탐색
        long left = 1; //랜선길이는 자연수므로  최솟값 1로 세팅해야함
        long right = max;
        while (left <= right) {
            long mid = (left + right) / 2;
            long sum = 0;
            for (int i = 0; i < K; i++) { // 자른 개수 합
                sum += (arr[i] / mid);
            }
            if (sum >= N) { //더 많은 랜선 나온 경우 더 크게 잘라줘야함
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        System.out.println(right);
    }
}

 

 

감사합니다. !