문제 1021 · 기초 4
인코딩 속도 정하기
이분 탐색 · 매개변수 탐색
테스트별 제한 2000ms · 브라우저 채점
문제
동영상 강의 N편을 밤사이에 인코딩해야 한다. i번째 영상의 크기는 a_i MB 다. 인코딩 서버의 속도를 분당 v MB 로 정하면 i번째 영상은 a_i ÷ v 를 올림한 분이 걸린다. 서버는 영상을 한 번에 한 편씩 차례로 처리하고, 영상 사이에 쉬는 시간은 없다. 주어진 T분 안에 모든 영상을 끝내려면 속도 v 를 최소 얼마로 정해야 하는가? v 는 1 이상의 정수다. 속도를 아무리 높여도 T분 안에 끝낼 수 없으면 -1 을 출력한다.
입력
첫째 줄에 N 과 T 가 주어진다. (1 ≤ N ≤ 30,000, 1 ≤ T ≤ 1,000,000,000) 둘째 줄에 a_1 … a_N 이 주어진다. (1 ≤ a_i ≤ 1,000,000)
출력
필요한 최소 속도 v 를 출력한다. 불가능하면 -1 을 출력한다.
예제 입력 1
3 10 30 12 25
예제 출력 1
8
예제 입력 2
4 3 1 1 1 1
예제 출력 2
-1
힌트 펼치기
- 속도가 빠를수록 총 시간은 줄어든다(늘지 않는다). 그러니 '속도 v 로 T분 안에 되는가?' 에 대해 이분 탐색을 할 수 있다.
- v 가 가장 큰 영상 크기 이상이면 영상마다 1분이 걸린다. 이때도 N > T 면 불가능하다.
관련 장
풀이 작성
코드는 서버로 전송하지 않습니다. 테스트가 공개되는 연습용 채점으로, 대회·인증용이 아닙니다.
풀이를 제출하면 여기에서 결과를 확인할 수 있습니다.
로그인 여부와 관계없이 이 브라우저에만 최근 제출 50개를 저장합니다.