[백준] 1561번 놀이 공원

문제 설명

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

문제 풀이

• 이분탐색을 이용하여 풀이하였다.
• 이분탐색의 대상은 특정 시간에 마지막 아이를 태울 수 있는지 여부로 판별하였다.

  • cal(long t) : 특정 시간에 해당 아이를 태우면 0, 이전에 태우면 -1, 이후에 태우면 1

• 해당 함수로 이분 탐색을 진행하여 타는 시간을 구하고 해당 시간에 몇번째 기구를 타는지를 구한다.

소스 코드 (JAVA)

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

public class Main{
    public static BufferedReader br;
    public static BufferedWriter bw;
    public static int N, M;
    public static int maxTime = 0;
    public static int[] time;

    // 해당 시간에 N번째 아이가 탄다면 -> 0
    // 해당 시간보다 이전에 N번째 아이가 탄다면 -> -1;
    // 해당 시간보다 이후에 N번째 아이가 탄다면 -> 1;
    public static int cal(long t) {
        long cnt = 0;
        long curInsertCnt = 0;
        for (int i = 0; i < M; i++) {
            if (t % time[i] == 0) {
                cnt += t / time[i];
                curInsertCnt++;
            } else
                cnt += (t / time[i]) + 1;
        }
        if (N <= cnt) return -1;
        else if (N > cnt + curInsertCnt) return 1;
        else return 0;
    }

    public static long binarySearch() {
        long lo = 0;
        long hi = N * (long)maxTime + 1;
        while(lo + 1 < hi) {
            long mid = (lo + hi) / 2;
            if (cal(mid) < 0) hi = mid;
            else lo = mid;
        }
        return lo;
    }

    public static int calResult(long t) {
        int cnt = 0;
        for (int i = 0; i < M; i++) {
            if (t % time[i] == 0)
                cnt += t / time[i];
            else
                cnt += (t / time[i]) + 1;
        }
        int cur = cnt;
        for (int i = 0; i < M; i++) {
            if (t % time[i] == 0) {
                if (++cur == N)
                    return i + 1;
            }
        }
        return 0;
    }

    public static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        time = new int[M];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < M; i++) {
            time[i] = Integer.parseInt(st.nextToken());
            maxTime = Math.max(maxTime, time[i]);
        }
    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        input();
        bw.write(calResult(binarySearch()) + "\n");
        bw.flush();
        br.close();
        bw.close();
    }
}