15810번: 풍선 공장
문제
전북대학교 프로그래밍 경진 대회에서는 ACM-ICPC 스타일을 따라 문제를 해결한 팀에게 그 문제에 해당하는 풍선을 달아준다.
풍선을 담당하는 N명의 스태프가 있다.
스태프마다 폐활량이 다르기 때문에 하나의 풍선을 만드는 데 걸리는 시간은 다양하다.
대회가 시작되고 운영진으로부터 M개의 풍선을 만들어 달라는 의뢰가 들어왔다!
각 스태프가 풍선 하나를 만드는 시간(분) Ai를 알고 있을 때, 풍선 M개를 만들기 위해서 최소 몇 분이 걸릴까?
풍선을 만든 후에 문제를 표시할 것이기 때문에 풍선의 종류는 상관이 없다.
모든 스태프는 풍선을 만드는 데에 정확하게 자신이 말한 시간만큼 걸린다.
예를 들어 스태프 A가 풍선 하나를 만드는 데 5분이 걸린다면, 0분에 만들기 시작해서 5분에 끝난다.
입력
스태프의 수 N과 풍선의 개수 M이 입력된다. (1 ≤ N, M ≤ 1 000 000)
다음 줄에 N명의 각 스태프들이 풍선 하나를 만드는 데 걸리는 시간 Ai가 순서대로 주어진다. Ai는 1 000 000 이하의 자연수이다.
출력
M개의 풍선이 다 만들어지는 최소 시간을 출력한다.
예제 1
3 8
5 7 314
힌트
1, 2, 3번 스태프가 각각 5분, 7분, 3분씩 걸린다면 3분이 지났을 때 3번 스태프가 1개, 5분에 1번 스태프가 1개, 6분에 3번 스태프가 1개를, 7분에 2번 스태프가 1개를, 9분에 3번 스태프가 1개를, 10분에 1번 스태프가 1개를, 12분에 3번 스태프가 1개를, 14분에 2번 스태프가 마지막 1개를 만들면 총 14분으로 최소 시간이 걸린다.
알고리즘 분류
- 이분 탐색
- 매개 변수 탐색
코드
1
1
https://www.acmicpc.net/problem/15810
15810번: 풍선 공장
1, 2, 3번 스태프가 각각 5분, 7분, 3분씩 걸린다면 3분이 지났을 때 3번 스태프가 1개, 5분에 1번 스태프가 1개, 6분에 3번 스태프가 1개를, 7분에 2번 스태프가 1개를, 9분에 3번 스태프가 1개를, 10분에
www.acmicpc.net
