개발자 톡
연습문제 톡
[21년 재직자 대회 예선] 마이크로서버
[21년 재직자 대회 예선] 마이크로서버 질문 시간초과
- 등록일
- 2021-11-17 08:38:38
- 조회수
- 836
- 작성자
- dbfl8969
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));
}
}
}
#[21년_재직자_대회_예선]_마이크로서버
#java
#binpacking