백준 1654번 - 랜선 자르기 / Java

문제

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

1654번: 랜선 자르기

이분 탐색을 활용하는 문제. 문제 자체는 어렵지 않았는데 자료형 선정에서 헤매었다.

랜선의 길이가 int의 최댓값이라 int로 될 줄 알았는데 이분 탐색과정에서 랜선의 길이를 서로 더하는 과정이 있어서

int형의 범위를 넘어서는 것을 인지 하지 못해서 틀렸다.

long으로 바꿔주니까 바로 정답이 나왔다.

 

알고리즘

1. 입력을 받으면서 가장 큰 길이의 랜선을 max에 저장해놓는다

2. 1~max까지로 범위를 잡고 이분 탐색을 진행해서 만들 수 있는 랜선의 개수를 센다

3. 만들 수 있는 랜선의 개수가 n보다 크거나 같을 경우 그때의 길이를 저장한다

4. n보다 크거나 같을 때 나온 랜선의 길이중 최댓값을 출력한다

소스코드

/*
 * BOJ1654
 * 2020.02.04
 * Hyeonseong 
 */
import java.util.*;    
public class BOJ1654 {
    public static void main(String[] args) {
        Solution s = new Solution();
    }
}
class Solution{
    int k;
    long n;
    long list[];
    public Solution() {
        Scanner scan = new Scanner(System.in);
        k = scan.nextInt(); // 이미 가지고 있는 랜선의 개수
        n = scan.nextLong(); // 필요한 랜선의 개수
        list = new long[k];
        long max = -1;
        for(int i=0;i<k;i++) {
            list[i] = scan.nextInt();
            if(max < list[i]) {
                max = list[i];
            }
        }
        long start = 1;
        long end = max;
        long maxLen = -1;
        while(start<=end) {
            long mid = (start+end)/2;
            long sum = 0;
            for(int i=0;i<list.length;i++) {
                sum+=list[i]/mid; // 현재 길이로 짤랐을때 나오는 랜선의 개수
            }
            if(sum >= n) { // 개수가 크거나같다면
                if(maxLen < mid) { // 가장 큰 길이만 저장한다
                    maxLen = mid;
                }
                start = mid+1;
            } else {
                end = mid-1;
            }
        }
        System.out.println(maxLen);
    }
}