BOJ 1654번 랜선 자르기

www.acmicpc.net/problem/1654

1654번: 랜선 자르기

 

접근

1. 가지고 있는 랜선을 잘라서 N개만큼 만들어야 한다.
2. 1부터 가지고 있는 랜선의 최대 길이 중 답을 찾아야 한다.
3. 이분탐색 고고

풀이

1. 랜선의 길이를 입력받을 때 최대 길이 저장
2. mid 값을 구하고 그 길이만큼 짤랏을 때 나오는 랜선 갯수 확인
3. N보다 크면 임시 답으로 저장 후 left = mid + 1 (랜선을 더 길게 짤라본다)
4. N보다 작으면 right - 1 (갯수를 늘려야 하기 때문에 랜선을 더 짧게 짤라본다)


중요 포인트!!

- 입력받는 랜선 길이가 2^32-1 까지인데 이 값을 입력받을 시
- int로 계산하게 되면 mid를 구하는 과정에서 overflow가 난다.
- long값으로 받아서 계산해야 한다!!!!

 

 

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

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

    static long stol(String s) {
        return Long.parseLong(s);
    }

    static int K, N;
    static long[] lan;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        K = stoi(st.nextToken());
        N = stoi(st.nextToken());

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

        long answer = 0;
        while(left <= right){
            long mid = (left + right) / 2;
            int current = check(mid);
            if(current >= N){
                left = mid + 1;
                answer = mid;
            } else {
                right = mid-1;
            }
        }

        System.out.println(answer);
    }

    static int check(long mid){
        int temp = 0;
        for (long i : lan) {
            temp += (i / mid);
        }

        return temp;
    }
}