1561 - 놀이 공원

문제: boj.kr/1561
날짜: 9월 8일 (일)
성공여부: X [01:30:34]

이분탐색 문제이다.

N이 20억이고 M이 1만이기 때문에 0분에 아이들을 M개의 놀이기구에 태우고 1분마다 한 명씩 태울 수 있는 곳에 태워서 모든 경우의 수를 찾는건 시간초과이다. 그럼 이를 효율적으로 찾는 방법을 생각해야 하는데, 이때 시간을 이용해 이분탐색을 하면 모두를 태우는 최적의 시간을 약 31번만에 더 빠르게 찾을 수 있다는 것까지는 생각했다.

하지만, 이 매개변수를 찾는 방법과 찾아서 활용하는 방법을 생각하지 못해서 해설을 봤다.

22 5
1 2 3 4 5

22명을 태우는 상황이라면 22명이 모두 타는 최적의 시간을 찾는다. 이 시간을 찾는 방법은 0분에 M(5)명을 일단 태우고 0~30*n까지 이분탐색을 진행하면서 mid값에 각 놀이기구의 시간을 나눈 몫을 더해서 ㅡ이 부분이 이해하기 어려웠는데, 만약 놀이기구가 운행시간이 3분이라고 한다면 전체 6분동안은 2명을 태울 수 있고 9분동안은 3명을 태울 수 있다. 이를 몫으로 구할 수 있는 것이다.ㅡ M(5) + 몫의 전체 합이 n명보다 크거나 같으면 시간을 더 줄여보고, n(22)명보다 작으면 해당 시간에는 n(22)명이 다 못타는 것이니 시간을 더 늘려가면서 최적의 시간을 찾아본다.

위 예제에서 해당하는 값을 찾아보면 22명의 경우 8분이 나온다.

8 / 1 = 8
8 / 2 = 4
8 / 3 = 2
8 / 4 = 2
8 / 5 = 1
= 17 + 5 = 22

그럼 8분에서 모두 다 탈 수 있는 것이니까 해당 시간의 1분 전 상황을 구해서 타고있는 인원을 구한다음 8분의 상황에서 탈 수 있는 놀이기구에 남은 인원을 태워보면 마지막으로 타는 인원의 놀이기구 번호를 찾을 수 있다.

코드

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

public class Main {
    // 시간제한 2초, 메모리제한 128MB

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        long[] play = new long[m];
        for (int i = 0; i < m; i++) play[i] = Integer.parseInt(st.nextToken());

        if (n <= m) System.out.println(n);
        else {

            long low = 0;
            long high = 30L * n + 1;

            while (low + 1 < high) {
                long mid = (low + high) / 2;

                long cnt = m;
                for (int i = 0; i < m; i++)
                    cnt += (mid / play[i]);

                if (cnt >= n) high = mid;
                else low = mid;
            }

            long ret = m;
            for (int i = 0; i < m; i++)
                ret += (low / play[i]);

            for (int i = 0; i < m; i++) {
                if (high % play[i] == 0) ret++;
                if (ret == n) {
                    System.out.println(i+1);
                    break;
                }
            }
        }
    }
}