[백준] 1561 놀이공원 -JAVA

1561번: 놀이 공원 (acmicpc.net)

1561번: 놀이 공원

매개변수 탐색의 개념을 잘 이해할 수 있는 좋은 문제

 

풀이

알고리즘 파악

이분탐색 (매개변수 탐색)

 

일반적인 매개변수 탐색 문제에서 조금 변형된 문제이다. 

문제의 핵심은 -> 몇 분에 아이들이 전부 탑승할 것인가? + 몇 번째 놀이기구에 마지막 아이가 탑승할 것인가?이다.

하나씩 살펴보면

 

1. 몇 분에 아이들이 전부 탑승할 것인가? -> 매개변수 탐색을 통해 시간을 구한다. begin=0 , end = 30*n으로 설정한다.

 

2. 몇 번째 놀이기구에 마지막 아이가 탑승할 것인가? ->

1번에서 구한 시간을 n이라 하면

 

총 놀이기구에 탑승할 아이들 수 - (n-1)분까지 놀이기구에 탑승한 아이들 수

= n분째에 놀이기구에 탑승할 아이들의 수

이다.

 

이 n분째에 놀이기구에 탑승할 아이들의 수를 for문을 통해 n분째 탑승 가능한 놀이기구에 하나씩 채워주면 된다.

전부 탑승하면 해당 놀이기구의 index를 출력하면 된다. 

 

import java.io.*;
import java.util.StringTokenizer;
public class Main {
	static int n,m,lastIdx,answer;
	static int[] arr;
	public static void main(String[] args) throws IOException{
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw  =new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());    
	    m=  Integer.parseInt(st.nextToken()); 
	    st = new StringTokenizer(br.readLine());
	    arr = new int[m];
	    
	    for(int i=0; i<m; i++)
	    {
	    	arr[i] = Integer.parseInt(st.nextToken());
	    }
        
		long begin=0;
	    long end = ((long)30*n);
        long min = 0;
        long max_time =0;
	    
	    while(begin<=end)
	    {
	    	long mid = (begin+end)/2;
	    	long result = search(mid);
	    	if(result<n) 
	    	{
                    begin=mid+1;
                    min =result; //(아이들이 전부 탐승 가능한 최소 분-1)분의 아이들의 수
	    	}
	    	else if(result>=n)
	    	{
                    end=mid-1;
                    max_time = mid; //아이들이 전부 탐승 가능한 최소 분    
	    	}
	    }
        
	    int cnt = n-(int)min; //추가적으로 세야할 아이들의 수
    	    for(int i=0; i<m; i++)
  	    {
  	    	if((max_time%arr[i])==0) //해당 시간에 스타트
  	    	{
  	    		cnt--;
  	    		if(cnt==0) answer=i+1;
  	    	}	
  	    }
  		bw.write(Integer.toString(answer));
        bw.flush();
        bw.close();
        br.close();
	}
	
	static long search(long time)
	{
		long cnt=0;
		for(int i=0; i<m; i++)
		{
		   long cnt_ = time/arr[i];
		   cnt+=cnt_+1;
		}
		return cnt;
	}
}