백준 1561번 : 놀이 공원 [Java]

https://www.acmicpc.net/problem/1561

 

문제 탐색하기 

꽤나 애를 많이 먹은 문제였다. 처음에는 여러 자료 구조를 이용해서 시간복잡도 안에 해결할 수 있을 듯하였다. 이에 따라서 M개의 놀이기구를 각각 HashMap (Python의 Dictionary)에 시간 별로 나누어 저장하고 매 시간 마다 계산 하도록 하였다... 

 

처음 생각했던 위 풀이는 공간 복잡도 (메모리 초과)로 통과할 수 없었는데 이는 매번 리스트를 생성 하고 저장하는 것과 HashMap에 리스트를 저장해야하는 것에서 비효율적이지 않나 생각된다. 하지만 위 풀이대로 한다해도 매번 1분씩 시간을 더했기 때문에 주어진 시간안에 연산할 수 없을 것이 분명했고 다른 방법을 생각했다.

 

N은 최대 20억, M은 1만이다. 1억번의 연산을 1초에 할 수 있다고 했을 때 우리는 N의 크기를 최소로 줄여야 시간안에 통과할 수 있게 된다. 그럼 어떤 식으로 찾아야 할까. 이분 탐색을 통해서 특정 시간에 몇명을 태웠는지를 계산하므로 써 우린 N의 시간을 줄일 수 있다.

 

이 때의 시간 복잡도는 O(Mlog(N)이므로 충분히 시간안에 연산이 가능한 숫자일 것이다.

 

이 때 N이 M보다 작거나 같으면 이분 탐색을 거칠 필요도 없다. N을 출력하면 된다.

 

여기서 중요한 점은 아이들은 0분에 놀이기구에 탑승할 수 있다는 점이다.

3번 예제를 표로 구현해보면 아래와 같다. (O는 아이들이 놀이기구에 탑승했다는 의미이다.)

	1	2	3	4	5
0	O	O	O	O	O
1	O
2	O	O
3	O		O
4	O			O
5	O				O
6	O	O	O
7	O
8	O	O		O

 

위 같은 연산을 구현할 때 자칫 잘못하면 N이 int 범위를 넘어갈 수 있기 때문에 long으로 연산을 하는 것이 중요하다. 그러면 최소 시간은 몇이 될 수 있을까?

M은 최소 1부터 30까지 될 수 있다. 이들의 최소 공배수를 구해보면 약 23조..인 숫자가 나오는데 N의 범위를 구하기엔 그보다 작은 범위여도 충분히 연산할 수 있다. 이에 따라서 이분 탐색의 high를 3e11 (300억) 정도의 숫자로 하여 구현하였다.

 

 

코드 설계하기

1. 입력을 처리한다.

2. N이 M보다 작거나 같으면 바로 N을 출력한다. 

3. 이분 탐색을 통해서 N보다 낮은 숫자가 찾아지는 시간을 이분 탐색을 통해서 탐색한다.

4. 얻어낸 숫자 값을 통해서 현재 몇명이 타고 있는 지 계산하고 N과 같아질 때의 번호를 찾는다.

5. 해당 값을 출력한다.

풀이

import java.util.*;
import java.io.*;

public class Main {
	static class FastReader {
		BufferedReader br;
		StringTokenizer st;

		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

        long nextLong() {
            return Long.parseLong(next());
        }
	}

    static long[] rides;

	public static void main(String[] args) {
		FastReader fr = new FastReader();
		long N = fr.nextLong();
		int M = fr.nextInt();

        if (N <= M) {
            System.out.println(N);
            return;
        }
        
        rides = new long[M];
		for (int i = 0; i < M; i++) {
			rides[i] = fr.nextLong();
		}

        long low = 0;
        long high = (long)3e11;
        long mid = 0;
        long count = 0;
        while (low < high) {
            mid = (low + high) / 2;
            count = 0;
            for (int i = 0; i < M; i++) {
                count += (mid / rides[i] + 1) ;
            }
            
            if (count < N) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        
        int answer = 0;
        
        if (count < N) {
            for (int i = 0; i < M; i++) {
                if (high % rides[i] == 0) {
                    count++;
                }
                
                if (count == N) {
                    answer = i + 1;
                    break;
                }
            }
        } else {
            long current = 0;
            high--; 
            
            for (int i = 0; i < M; i++) {
                current += (high / rides[i] + 1);
            }
            
            high++;
            
            for (int i = 0; i < M; i++) {
                
                if (high % rides[i] == 0) {
                    current++;
                }
                
                if (current == N) {
                    answer = i + 1;
                    break;
                }
            }
        }
        
        System.out.println(answer);
	}
}