백준 - 랜선 자르기

문제

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

1654번: 랜선 자르기

 

 

풀이

결정 문제로 바꿔 랜선이 몇 센치미터 이상부터 문제 결과를 만족하는지 찾는다.

랜선의 최대 길이가 int 값의 최대 값이므로 long 변수를 사용해서 중간 계산을 진행한다.

 

 

코드

java

import java.util.Scanner;

public class Main {
    static int k, n;
    static int[] a;
    
    public static void main(String[] args) {
        input();
        solve();
    }
    
    private static void solve() {
        long l = 1;
        long r = Integer.MAX_VALUE;
        long res = 0;
        while (l <= r) {
            long h = (l + r) / 2;
            if (validate(h)) {
                l = h + 1;
                res = h;
            } else {
                r = h - 1;
            }
        }
        System.out.println(res);
    }
    
    private static boolean validate(long h) {
        long cnt = 0;
        for (int i = 0; i < a.length; i++) {
            cnt += a[i] / h;
        }
        return cnt >= n;
    }
    
    private static void input() {
        Scanner sc = new Scanner(System.in);
        k = sc.nextInt();
        n = sc.nextInt();
        a = new int[k];
        for (int i = 0; i < k; i++)
            a[i] = sc.nextInt();
        sc.close();
    }
}