백준 1561 놀이공원 Java

이분 탐색 문제인 놀이공원이다.

아무정보없이 이 문제를 만났다면

이분탐색으로 풀릴 거라는 생각도 못했을 것이다.

여태까지 풀어본 다른 이분 탐색 문제들과는 조금 다르다.

 

수를 딱 정해서 이분탐색으로 그 범위를 줄여나가는 것이 아닌

N번째 학생이 탈 놀이기구의 번호,

N번째 학생이 정해져있다.

놀이기구의 번호로 범위를 줄여나갈 순 없을 것이다.

 

이 문제는 시간으로 범위를 설정해야 한다.

놀이기구의 개수 m이 주어지고

각각의 놀이기구 운영 시간이 주어지기 때문이다.

 

x분까지 놀이기구를 탄 학생의 수를 구해서 end에 넣고

x분에 놀이기구를 탄 학생의 수를 구해서 end에서 뺀다음 begin에 넣고

그 사이에(begin <= n <= end) n번째 학생이 있다면

n번째 학생이 탄 놀이기구의 번호를 출력하면 된다.

 

다른 문제들과 마찬가지로 n의 범위가 begin과 end사이가 아니라면

x분을 늘리거나 줄이거나 하면 된다.

 

예제의 상황에서 0분부터 12분까지의 학생 상황이다.

백준님의 강의자료 중..

0분에는 아무도 놀이기구에 타있지 않으므로

5개의 놀이기구에 다 타면 되고 그 후엔

각각의 운영시간 별로 학생이 타게된다

 

x분까지 몇명의 학생이 놀이기구를 탔는지 구하고 싶다면

x분에 각각의 운영시간을 나눈 값을 더하면 된다.

예를 들어 8분까지 탄 학생의 수라면

8/1 + 8/2 + 8/3 + 8/4 + 8/5 -> 8+4+2+2+1 ->17에

0분에 탄 m명의 학생수를 더하면 된다. -> 17+5 -> 22명

 

x분에 탄 학생의 수를 구하고 싶다면

x분에 각각의 운영시간을 나머지 연산했을 때 0인 수를 구하면 된다.

예를 들어 8분에 탄 학생의 수라면

8%1 == 0,  8%2 == 0,  8%4 ==0 -> 3명

8분에는 1번놀이기구에 1명이타고, 2번 놀이기구에 1명이타고, 4번 놀이기구에 한명이 탄것이다.

 

이런식으로 x분까지탄 학생의 수를 end에, x분에 탄 학생의 수를 end에서 뺀다음 begin에 넣고

그 범위안에 n번째 학생이 타있다면

n번째 학생이 몇 번째 놀이기구를 탔는지 아까와 같은 %연산으로 찾으면 된다.

 

주의할 점은 시작하는 범위에 x분에 탄 첫 번째 학생을 포함시켜줘야 한다.

8분까지 탄 학생의 수는 22명 8분에 탄 학생의 수는 3명

22 - 3이면 19로 7분까지 탄 학생의 수가 나온다.

범위를 정할 때 8분에 탄 학생 수 부터 8분까지 탄 학생의 수를 범위로 정해야 하므로

8분에 탄 학생의 수 3명을 빼고 +1을 다시 해줘야 한다.

 

처음 범위는 시간의 최소범위인 0분과 최대범위인 2000000000(n의 최대) * 30(시간의 최대) 이다.

그리고 중간값으로 계속 비교해나가는 기존의 방식대로 한다.

 

import java.util.Scanner;
 
public class Q1561 {
 
     public static void main(String args[]) {
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            int m = sc.nextInt();
            int[] a = new int[m];
            for (int i=0; i<m; i++) {
                a[i] = sc.nextInt();
            }
            if (n <= m) {
                System.out.println(n);
                return;
            }
            long left = 0;
            long right = 2000000000L * 30L; //N최대 * 소요시간 최대 30분
            while (left <= right) {
                long mid = (left + right) / 2;
                long begin = 0;
                long end = m;
                for (int i=0; i<m; i++) {
                    end += mid/a[i];
                }
                begin = end;
                for (int i=0; i<m; i++) {
                    if (mid % a[i] == 0) {
                        begin -= 1;
                    }
                }
                begin += 1;
                if (n < begin) {
                    right = mid-1;
                } else if (n > end) {
                    left = mid+1;
                } else {
                    for (int i=0; i<m; i++) {
                        if (mid % a[i] == 0) {
                            if (n == begin) {
                                System.out.println(i+1);
                                return;
                            }
                            begin += 1;
                        }
                    }
                }
            }
 
        }
}