백준 15810 풍선공장
-
백준 15810 풍선 공장Algorithm/BOJ 2021. 3. 3. 00:17
출처: www.acmicpc.net/problem/15810 분류: 이분탐색 접근방식 스태프 한 명이 만들 수 있는 풍선의 개수는 시간 / 걸리는 시간 으로 구해줄 수가 있고 특정 시간에 만들어진 풍선의 개수는 해당 시간에 각 스태프가 만들 수 있는 풍선의 개수를 모두 더해 구할 수 있습니다. 이제 최대 걸리는 시간을 특정할 수 있다면 각 시간에 원하는 풍선 개수를 넘거나 같은 시간을 찾아 이분 탐색으로 반씩 잘라가며 찾을 수 있습니다. 처음으로 풍선의 개수를 넘거나 같은 시간을 찾아야 하기 때문에 이분탐색 lower bounded 로 풀어줬습니다. 마지막으로 최대 걸리는 시간(High)을 정해줘야 합니다. 처음에는 staff의 최대 범위가 1000000이여서 적당히 원하는 풍선의 개수 * 1000000..