아직 계정이 없으신가요? 회원가입

Dev. Talk

[21년 재직자 대회 예선] 마이크로서버 질문 시간초과

회원사진dbfl8969
108 views2021-11-17 08:38

Bin packing 으로 풀어보았는데, 2번째 케이스까지는 통과가 되는데 결국 시간초과가 납니다.

이중 for문을 binary search를 사용하면 해결 할 수 있을 거 같은데

잘 풀리지가 않네요.. 도움주실분 계신가요~?





public class Main {

    static int firstFit(Integer weight[], int n, int c)
    {
        int res = 0;

        int[] bin_rem = new int[n];

        for (int i = 0; i < n; i++) // 3개
        {

            int j;
            for (j = 0; j < res; j++) //생성된 서버개수만틈 실행
            {
                if (bin_rem[j] >= weight[i])
                {
                    bin_rem[j] = bin_rem[j] - weight[i];  break;
                }
            }

            if (j == res)
            {
                bin_rem[res] = c - weight[i];
                res++;
            }



        }
        return res;
    }

    static int firstFitDec(Integer weight[], int n, int c)
    {

        Arrays.sort(weight, Collections.reverseOrder());
        return firstFit(weight, n, c);
    }

    // Driver code
    public static void main(String[] args)
    {


        Scanner sc = new Scanner(System.in);
        int c = 900;
        int N = sc.nextInt();
        for(int i = 0; i< N; i++){
            int t = sc.nextInt();
            Integer weight[] = new Integer[t];

            for(int j = 0; j < t ; j++){
                weight[j] = sc.nextInt();
            }
            System.out.println(firstFitDec(weight,t,c));
        }
    }

}