[백준] 1561번 : 놀이 공원

문제

www.acmicpc.net/problem/1561

1561번: 놀이 공원

문제해결방법

놀이기구를 타는 시간을 기준으로 0초와 놀이기구를 탈 수 있는 마지막 시간을 양 끝으로 하고,

해당 시간대에 탈 수 있는 인원의 수를 구하고 그 인원이 N을 넘는지를 기준으러 그 사이의 시간을 이진탐색 한다.

위 탐색으로 N을 넘는 가장 작은 시간을 구하고 그 시간대에 탈 수 있는 총 인원의 수와 N의 차이를 구한다.

그 차이만큼 탈 수 있는 놀이기구를 뒤에서부터 세서 어떤 놀이기구를 타는지 구해준다.

코드

package baekjoon;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main1561_놀이공원 {
    
    public static long getCapacity(int[] times, long t) {
        long capacity = 0;
        for(int i=0; i<times.length; i++) capacity += t/times[i]+1;
        return capacity;
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long N = Long.parseLong(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[] times = new int[M];
        st = new StringTokenizer(br.readLine());
        int max = 0;
        for(int i=0; i<M; i++) {
            times[i] = Integer.parseInt(st.nextToken());
            if(max<times[i]) max=times[i];
        }
        long s = 0, e = (N/M+1)*max;
        while(s<=e) {
            long mid = (s+e)>>1;
            long cap = getCapacity(times, mid);
            if(cap<N) s = mid+1;
            else e = mid-1;
        }
        long cap = getCapacity(times, s);
        long index = cap - N;
        int answer = 0;
        for(int i=times.length-1; i>=0; i--) {
            if(s%times[i]==0) {
                if(index==0) {
                    answer = i+1;
                    break;
                }
                index--;
            }
        }
        System.out.println(answer);
        br.close();
    }
}

코드에 대한 피드백이나 더 좋은 아이디어는 언제나 환영입니다.