[BOJ 1654] 랜선 자르기 (Java)

문제

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

1654번: 랜선 자르기

 

풀이

이분 탐색을 이용해 풀 수 있다. 

예시 

3 5
5
5
4

오영식이 이미 가지고 있는 랜선의 개수가 3개

5

5

4

 

내가 필요한 랜선의 개수는 5개이다. 

이 조건이 충족될 때까지 이분 탐색을 진행한다. 

 

초기 값 

left = 1

right = 5

 

첫 번째 탐색

left = 1

right = 5

mid = 3

 

5, 5, 4 를 3으로 나눈 몫을 모두 더하면 랜선의 개수를 구할 수 있다. 

3의 길이로 랜선을 잘랐을 때, 3개의 랜선을 얻음을 알 수 있다. 

내가 원하는 랜선은 5개 이므로 3개의 랜선은 부족하다. 

따라서 right를 mid-1로 갱신하여 길이의 범위를 줄여서 다시 탐색한다.

 

두 번째 탐색 

left = 1

right = 2

mid = 1

 

1로 잘랐을 때, 랜선의 개수는 9개이다.

left 를 mid +1로 갱신하여 재 탐색한다. 

 

세번 째 탐색 

left = 2

right = 2

mid = 2

 

2로 잘랐을 때, 랜선의 개수가 5개이다. 

이때의 mid값이 답이 된다.

 

 

소스코드

package binarysearch;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ1654 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        // 이미 가지고 있는 랜선 K, 필요한 랜선 개수 N
        int K = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        int[] rans = new int[K];

        long left = 1;
        long right = 0;
        for(int i = 0; i < K; i++){
            rans[i] = Integer.parseInt(br.readLine());
            right = Math.max(right, rans[i]);
        }

        long ans = 1;
        while(left <= right){
            long mid = (left + right)/2;
            if(getCount(rans, mid) >= N){
                // mid 길이로 가지고 있는 랜선을 짤랐을 때, 필요한 랜선 개수 N이상 으로 나옴.
                // 더 길게 자르자
                ans = mid;
                left = mid + 1;
            } else {
                // mid 길이로 가지고 있는 랜선을 짤랐을 때, 필요한 랜선 개수 N 미만으로 나옴.
                // 더 짧게 자르자
                right = mid -1;

            }
        }
        System.out.println(ans);
    }

    public static int getCount(int[] rans, long mid){
        int cnt = 0;
        for(int i = 0; i < rans.length; i++){
            cnt += rans[i]/mid;
        }
        return cnt;
    }
}