개발자 크루
박희진교수의 2024년 2학기 수업에 수강신청한 학생만 들어올 수 있습니다. 신청사유에 학번과 이름을 꼭 기재해 주기 바랍니다.
21년 재직자 대회 예선
[21년 재직자 대회 예선] 마이크로서버
- 난이도
- 3 단계
- 참가자
- 35 명
- 제출
- 209 명
- 정답률
- 20.57 %
언어별 시간/메모리
| 언어 | 시간 | 메모리 |
|---|---|---|
| JavaScript | 3초 | 1024MB |
| C | 1초 | 1024MB |
| C++ | 1초 | 1024MB |
| Java | 3초 | 1024MB |
| Python | 3초 | 1024MB |
당신은 현대자동차그룹의 다양한 부서들이 사용하는 마이크로서비스들이 정상적으로 실행될 수 있도록 클러스터를 관리하는 업무를 맡고 있다.
클러스터는 여러 대의 마이크로서버로 구성되어 있다. 각각의 마이크로서버는 정확히 1000MiB의 메모리(RAM)를 갖고 있는데, 이 중 100MiB는 예비용으로 남겨 두기 때문에, 실제로 애플리케이션들이 사용할 수 있는 메모리는 총 900MiB이다. 하나의 마이크로서버에 여러 개의 마이크로서비스를 실행할 수 있는데, 이 때 마이크로서비스들이 사용하는 메모리의 총합은 900MiB를 넘을 수 없다. 현재 총 N개의 마이크로서비스가 실행 대기중이다. 이 중 i (1 ≤ i ≤ N)번째 서비스는 정확히 mi MiB의 메모리를 요구한다. 각각의 서비스는 최소 300MiB, 최대 900MiB의 메모리만을 요구하고 있다.
모든 마이크로서비스들을 실행하기 위해 최소 몇 대의 마이크로서버가 필요한지 구하는 프로그램을 작성하라.
제약조건
주어지는 모든 수는 정수이다.
하나의 입력에서 1개 이상 1,000개 이하의 테스트 케이스를 해결해야 한다.
각각의 테스트 케이스에 대해:
* 1 ≤ N ≤ 100,000
* 모든 i (1 ≤ i ≤ N)에 대해, 300 ≤ mi ≤ 900
하나의 입력에서 주어지는 모든 N의 합은 200,000 이하이다.
입력형식
첫 번째 줄에 테스트 케이스의 개수 T가 주어진다. 이후 아래와 같은 형식으로 2·T개의 줄에 T개의 테스트 케이스들이 주어진다. 이후 해당 케이스의 정보가 이어서 첫 번째 줄에 N이 주어진다. 두 번째 줄에 m1, m2,…, mN이 공백 하나씩을 사이로 두고 주어진다.
출력형식
각각의 테스트 케이스에 대해, 한 줄에 하나씩, 순서대로, 필요한 최소 마이크로서버의 수를 출력한다.
입력예제1
2 3 300 300 300 4 300 300 300 300
출력예제1
1 2
입력예제2
3 2 300 400 2 800 900 5 500 501 350 400 444
출력예제2
1 2 3