[백준] 1561 놀이공원 java 풀이

1. 문제 설명 📌

문제 링크

2. 구현 방법 🗃️

KEY WORD: BINARY_SEARCH, PARAMETRIC_SEARCH

N: 놀이기구 타는 아이 수, M: 놀이기구 수, rids[] = 놀이기구 별 걸리는 시간,
minimum_time: 애들 전부 놀이기구에 태우는 최소 시간,
remained_kid: (minimum_time -1 ) 시간에 아직 놀이기구 못 타고 남아있는 아이들의 수

• 0️⃣ 사람 수 < 놀이기구 수 이면, 마지막 사람의 번호가 곧 놀이기구의 수 이므로 N 출력 후 프로그램 종료
• 1️⃣ 아이들을 다 태울 수 있는 최소 시간 찾기 (minimum_time)
• 2️⃣minimum_time 1분 전 시점까지 아직 놀이기구 못 탄 아이들이 몇 명인지 찾기 (remained_kid)
• 3️⃣ rids[]를 돌며, (rides[]% minimum_time == 0)인 놀이기구를 만날 때마다 remained_kid --
• 4️⃣ remained_kid = 0 인 된 시점의 ride[] 번호가 곧 답

(1) 해설

1️⃣ K분에 아이들이 누적 몇 명 놀이기구에 탔는지 확인하는 방법✨

다음은 문제 예제 3번 아이 수: 22, 놀이기구 수: 5, 각각 걸리는 시간: [1,2,3,4,5]에 대한 표이다. 시간 단위를 분으로 놓았을 때, 각 시간마다 놀이기구에 탔으면 .으로 표시했다.

0분째는 모든 놀이기구에 다 탄다. 0분째 탄 경우를 제외하고 보면, 놀이기구 i의 K분 누적 손님은 K/놀이기구 걸리는 시간 이다. 예를 들어 1번 놀이기구는 1분마다 탈 수 있는데, 8분째에 총 8명이 누적해서 탄 것을 확인할 수 있다. 4번 놀이기구는 8분째에 총 2분이 탔다.
여기서 중요한 점은 0분째 탄 경우는 제외한다는 것이다. 만약 해당 경우도 누적에 포함시키면 매 계산마다 + 1을 해줘야 해서 번거롭다. 따라서 필자도 0분째 탄 인원 수는 미리 제하고 계산할 예정이다.

2️⃣ 모든 어린이가 다 탈 수 있는 최소 시간 찾기

우리는 이제 K분에 손님이 누적해서 얼마나 탔는지 한 번의 Loop로 알 수 있게 되었다. 이제 Parametric Search 접근 방법을 활용해 최적화 문제를 여러 개의 결정 문제로 바꿀 시간이다. 다음과 같이 바꾸면 된다.

N명이 전부 타는 최소 시간 구하기 ➜ mid 분에 모든 아이들이 놀이기구에 탈 수 있는가? (f(d))

결정 문제인 f(d)는 해설 1️⃣에서 구했음으로 이제, 이를 이용해 이분 탐색을 하여 f(d) = true인 값 중 제일 왼쪽에 있는 값을 찾으면 된다.

3️⃣ remained_kid 구하는 이유

해당 문제가 골드 1인 이유는 최소 시간 자체를 구하는 것이 아니라, 마지막으로 타는 놀이기구의 번호를 구하도록 한 번 더 꼬았기 때문이다. remained_kid는 이를 위해 필요하다. 마지막 놀이기구 번호를 구하는 방법은 다음과 같다.

• ❶ 모든 아이들이 전부 타는 최소 시간을 k라고 했을 때, k-1분에 못 타는 아이들 구하기 (이 애들은 K분에 타는 애들임)
• ❷ 이제 remained_kid를 한 명씩 태우며 마지막 놀이기구 번호를 구한다.

4️⃣ K분에 해당 놀이기구가 비었는지 어케 앎?

아까 우리가 매 분마다 아이들을 놀이기구에 태웠을 때를 기억하는가? 2분마다 비는 놀이기구는 2,4,6분에 태웠고, 3분 마다 비는 놀이기구는 3,6에 태웠다. 이 놀이기구는 분명 9분에도 비어있을 것이다. 즉 현재를 k분이라 하면k/놀이기구의 걸리는 시간의 나머지가 0인 순간이 바로 놀이기구가 비어 있는 순간이다.

위의 예시에서도 8분째에 비어 있는 놀이기구는 1,2,4번 놀이기구 였다.

(2) 시간복잡도 분석 🕓

N: 놀이기구 타는 아이 수, M: 놀이기구 수

• 놀이기구 시간 입력: $O(M)$
• 모두 태우는 최소 시간 구하기: $O( 30N \log 30N)$ (30 = 놀이기구 이용에 걸리는 시간의 최대값)
• 최소 시간 되는 지 확인: $O(M)$
• remained_kid 구하기 : $O(M)$
• 답 구하기: $O(M)$

총 시간 복잡도: $O(M + 30N \log 30N)$

3. 코드 소개 🔎

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class Main {
    static int N, M;
    static long minimum_time, remained_kid;
    static int [] rides;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        rides = new int [M];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            rides[i] = Integer.parseInt(st.nextToken());
        }

        if(M >= N) {    // 놀이기구보다 사람수가 적거나 같을 경우, 사람의 순번이 곧 타는 놀이기구
            System.out.println(N);
            return;
        }
        N -= M;
        minimum_time = binary_search();
        remained_kid = N - before_minimum_time_kiddo_cnt(minimum_time);
        System.out.println(last_rides_num(remained_kid));
    }
    // N명의 아이를 모두 태울 수 있는 최소 시간 찾는 함수
    public static long binary_search() {
        long start  = 0;
        long end    = 30 * (long)Integer.MAX_VALUE;
        while (start <= end) {
            long mid = (start + (end - start)/2);
            if(f(mid)) end = mid -1;
            else start = mid + 1;
        }
        return start;
    }
    // N명을 입력 받은 시간 내로 모두 태울 수 있으면 true, 아니면 false 반환하는 함수
    public static boolean f(long time) {
        long kids = 0;
        for (int i = 0; i < M; i++) {
            kids += time/rides[i];
        }
        return N <= kids;
    }

    // 최소시간 - 1분 시점에 남아있는 아이 수 구하는 함수 
    public static long before_minimum_time_kiddo_cnt( long minimum_time){
        long kids = 0;
        for (int i = 0; i < M; i++) {
            kids += (minimum_time-1)/rides[i];
        }
        return kids;
    }

    // 마지막 놀이기구 번호 구하는 함수
    public static int last_rides_num(long kids_cnt) {
        for (int i = 0; i < M; i++) {
            if(minimum_time%rides[i] == 0) kids_cnt--;
            if(kids_cnt == 0) return i+1;
        }
        return -1;
    }
}

4. 배운 것들 🎯

문제를 이렇게도 낼 수 있구나 배웠다.