백준(BOJ) 1654 : 랜선 자르기 (JAVA)

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

1654번: 랜선 자르기

 

결론부터 말하자면, 이 문제는 이분탐색 문제이다. 이분탐색으로 풀면된다는 사실을 알고 이 문제를 보면, 사실 그다지 어려운 문제는 아니다. 근데 이분탐색으로 풀면 되겠다고 생각해내는 것, 그게 어렵다. 어쩌면 그게 알고리즘의 전부일지도 모르겠다...ㅠㅠ

 

그리고 이 문제의 정답비율이 유독 낮은(현재 19%) 이유를 필자가 예상하건데, 함정이 있다. 문제에서는 랜선의 길이가 2^31 -1(int의 최댓값)보다 작거나 같은 자연수라고 나오는데, 이는 랜선의 길이를 int로 해도 되겠다라고 생각하게 만들지만 그렇지 않다. 이분 탐색을 위해 두 길이를 더하는 순간 넘어가버리게 된다... 코드는 아래와 같다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int k = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());
        int[] wires = new int[k];
        long sum = 0;
        
        for(int i = 0; i < k; i++) {
            wires[i] = Integer.parseInt(br.readLine());
            sum += wires[i];
        }
        
        long answer = 1;
        long left = 1;
        long right = sum / n;
        
        while(left <= right) {
            long mid = (left + right) / 2;
            
            int cnt = checkPossibleLineNo(wires, mid, k);
            
            if(cnt >= n) {
                left = mid + 1;
                
                if(mid > answer) {
                    answer = mid;
                }
            } else {
                right = mid - 1;
            }
        }
        
        System.out.println(answer);
    }
 
    private static int checkPossibleLineNo(int[] wires, long mid, int k) {
        int cnt = 0;
        
        for(int i = 0; i < k; i++) {
            cnt += wires[i] / mid;
        }
        
        return cnt;
    }
}