[CodingTest] 백준 1654번

현재까지 푼 코딩테스트 중에 난이도도 제일 높고 시간도 제일 오래 걸린 문제였다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static long[] arrays;
    static long key;

    static long Binary_Search(long start, long end) {
        if (start > end) return -1;

        long mid = (start + end) / 2;
        long total = 0;
        for (long x : arrays) {
            total += x / mid;
        }

        if (total >= key) {
            return Math.max(mid, Binary_Search(mid + 1, end));
        } else {
            return Binary_Search(start, mid - 1);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long[] k_n = stringsToInts(br.readLine().split(" "));
        arrays = new long[(int) k_n[0]];
        key = k_n[1];
        long sum = 0;
        long max = 0;
        for (int i = 0; i < arrays.length; i++) {
            arrays[i] = Long.parseLong(br.readLine());
            sum += arrays[i];
            if (arrays[i] > max) {
                max = arrays[i];
            }
        }

        System.out.println(Binary_Search(1, max));
    }

    static long[] stringsToInts(String[] s) {
        long[] longs = new long[s.length];
        for (int i = 0; i < s.length; i++) {
            longs[i] = Integer.parseInt(s[i]);
        }
        return longs;
    }
}

======================

밑 코드들은 실패한 재귀함수와 

분할탐색을 안쓰고 푼 예시이다.

static long Binary_Search(long start, long end){
    if(start >= end){
        return start;
    }
    long mid = (start+end)/2;
    long total = 0;
    for(long x : arrays) {
        total += x / mid;
    }

    if(total >= key) return Binary_Search(mid,end);
    else return Binary_Search(start,mid-1);
}

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long[] k_n = stringsToInts(br.readLine().split(" "));
        long[] lan_CM = new long[(int)k_n[0]];
        long sum=0;

        for (int i = 0; i < lan_CM.length; i++) {
            lan_CM[i]=Long.parseLong(br.readLine());
            sum+=lan_CM[i];
        }
        long end = Math.round((float)sum/k_n[1]);

        System.out.println(list_setting(lan_CM,end,k_n[1]));
    }
    static int list_setting(long[] arrays, long end, long n){
        Arrays.sort(arrays);
        long[] tmp_array;
        long total;
        int j;
        for (int i = (int)end; i > 0; i--) {
            total=0;
            tmp_array = arrays.clone();
            for (j = 0; j < arrays.length; j++) {
                tmp_array[j] = (long) Math.floor((double)tmp_array[j]/ i);
                total+=tmp_array[j];
            }
            if(total>=n)
                return i;
        }
        return -1;
    }

    static long[] stringsToInts(String[] s){
        long[] longs = new long[s.length];
        for(int i = 0; i < s.length; i++){
            longs[i] = Integer.parseInt(s[i]);
        }
        return longs;
    }
}