[Boj_1561] 놀이 공원

📎 문제 링크

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

 

▸ 문제

N명의 아이들이 한 줄로 줄을 서서 놀이공원에서 1인승 놀이기구를 기다리고 있다. 이 놀이공원에는 총 M종류의 1인승 놀이기구가 있으며, 1번부터 M번까지 번호가 매겨져 있다.

모든 놀이기구는 각각 운행 시간이 정해져 있어서, 운행 시간이 지나면 탑승하고 있던 아이는 내리게 된다. 놀이 기구가 비어 있으면 현재 줄에서 가장 앞에 서 있는 아이가 빈 놀이기구에 탑승한다. 만일 여러 개의 놀이기구가 동시에 비어 있으면, 더 작은 번호가 적혀 있는 놀이기구를 먼저 탑승한다고 한다.

놀이기구가 모두 비어 있는 상태에서 첫 번째 아이가 놀이기구에 탑승한다고 할 때, 줄의 마지막 아이가 타게 되는 놀이기구의 번호를 구하는 프로그램을 작성하시오.

 

▸ 입력

첫째 줄에 N(1 ≤ N ≤ 2,000,000,000)과 M(1 ≤ M ≤ 10,000)이 빈칸을 사이에 두고 주어진다. 둘째 줄에는 각 놀이기구의 운행 시간을 나타내는 M개의 자연수가 순서대로 주어진다. 운행 시간은 1 이상 30 이하의 자연수이며, 단위는 분이다.

 

▸ 출력

첫째 줄에 마지막 아이가 타게 되는 놀이기구의 번호를 출력한다.

 

📍 문제 정보

• 🥇  문제 레벨 : 골드 1
• 🔔  문제 유형 : 이분 탐색, 매개 변수 탐색
• 💬  풀이 언어 : JAVA

 

🤔 문제 풀이

이 문제는 단순히 선형 탐색으로 접근하면, 아이들의 수가 최대 20억 명까지 될 수 있기 때문에 시간 초과가 발생하게 된다.

따라서 이 문제는 이분 탐색을 활용하여 해결할 수 있다.

 

⏱ 아이들이 탑승한 인원을 시간 기준으로 계산하기

핵심 아이디어는, 특정 시간 t가 주어졌을 때, 그 시점까지 몇 명의 아이가 놀이기구를 탔는지 계산하는 것이다.

• 0분에는 모든 놀이기구가 한 번씩 운행을 시작하므로, 처음 m명의 아이들이 즉시 탑승한다.
• 이후 각 놀이기구는 자신의 운행 시간이 지날 때마다 반복적으로 아이들을 태울 수 있기 때문에, 각 놀이기구는 t / time[i]만큼의 아이를 추가로 태울 수 있다.

private static long getChildNumInTime(long t) {
    long childNum = m;
    for (int i = 0; i < m; i++) {
        childNum += t/time[i];
    }

    return childNum;
}

 

🧠 이분 탐색으로 최소 시간 찾기

그럼 이제 N번째 아이가 놀이기구를 탈 수 있는 최소 시간을 이분 탐색으로 찾아야 한다.

• 모든 아이들이 놀이기구를 타는 데 걸릴 수 있는 최대 시간은 n * 30분으로 설정할 수 있다.
  • 가장 극단적은 상황인 20억 명의 아이들이 운행 시간이 30분인 1개의 놀이기구만 이용하는 경우
• 이분 탐색을 통해 해당 시간 안에 n명 이상이 탑승 가능한지를 체크하면 범위를 좁혀나간다.

private static long binarySearch() {
    long left = 0;
    long right = n*30;

    while (left <= right) {
        long mid = (left+right)/2;
        long childNum = getChildNumInTime(mid);

        if (childNum < n) {
            left = mid+1;
        } else {
            right = mid-1;
        }
    }

    return left;
}

• getChildNumInTime(mid)는 mid 시점까지 놀이기구를 탄 아이들의 총 수를 반환한다.
• 이 값이 n보다 작으면 아직 N번째 아이가 탈 수 없는 시간이므로 left를 늘리고,
• 그렇지 않다면 조건을 만족하는 시간이므로 right를 줄여 더 빠른 시간대를 탐색한다.

최종적으로 left에는 N번째 아이가 탑승 가능한 최소 시간 t가 담기게 된다.

 

🎯 마지막 아이가 탄 놀이기구 찾기

이제 우리가 알고 싶은 것은, N번째 아이가 어떤 놀이기구를 탔는지이다.

• 먼저 t-1 시점까지 놀이기구를 탄 아이들의 수를 계산한다.
• 이제 t 시점에서 비게 되는 놀이기구들을 차례로 확인하면서, 아이들을 순서대로 태운다.
• 그중 N번째 아이가 탑승하게 되는 순간, 해당 놀이기구의 번호를 출력하면 된다.

long child = getChildNumInTime(min-1); // min은 최소 시간
for (int i = 0; i < m; i++) {
    if (result%time[i] == 0) {
        child++;
    }
    if (child == n) { 
        System.out.println(i+1);
        break;
    }
}

• result%time[i] == 0이라는 조건은 놀이기구 i가 t 시점에 아이를 태울 수 있는 상태임을 의미한다.
• 이 조건을 만족하는 놀이기구들을 번호순으로 확인하면서 아이를 태운다.
• 누적한 아이 수가 n번째가 되는 순간, 해당 놀이기구가 바로 N번째 아이가 탑승한 놀이기구가 된다.

 

위 풀이의 코드를 바탕으로 전체적인 코드를 작성해 보면 아래와 같다.

 

✔ 코드

메모리 : 13196KB
시간 : 108ms

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

public class Main {
    static long n;
    static int m;
    static int[] time;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Long.parseLong(st.nextToken()); // 아이들 수
        m = Integer.parseInt(st.nextToken()); // 놀이기구 종류

        st = new StringTokenizer(br.readLine());
        time = new int[m]; // 각 놀이기구의 운행 시간
        for (int i = 0; i < m; i++) {
            time[i] = Integer.parseInt(st.nextToken());
        }

        // 아이들 수가 놀이기구 종류보다 작다면
        // 모두 바로 탑승 가능
        if (n <= m) {
            System.out.println(n);
            return;
        }

        long min = binarySearch(); // n번째 아이까지 탑승 가능한 최소 시간
        long child = getChildNumInTime(min-1); // n번째 아이가 탑승하기 직전까지 탑승한 아이 수

        for (int i = 0; i < m; i++) {
            if (min%time[i] == 0) { // 놀이기구 i는 새 아이를 태울 준비가 된 상태
                child++; // 한 명 탑승
            }
            if (child == n) { // 모두 탑승했다면
                System.out.println(i+1); // 마지막 아이가 타게 되는 놀이기구의 번호 출력
                break;
            }
        }

        br.close();
    }

    private static long binarySearch() {
        long left = 0; // 최소 시간
        long right = n*30; // 최대 시간, 모든 아이들이 놀이기구를 탈 수 있는 최대 시간

        while (left <= right) {
            long mid = (left+right)/2;
            long childNum = getChildNumInTime(mid); // mid 동안 놀이기구를 탈 수 있는 아이들의 수

            if (childNum < n) {
                left = mid+1;
            } else {
                right = mid-1;
            }
        }

        return left;
    }

    private static long getChildNumInTime(long t) {
        long childNum = m; // 0분에 아이들이 차례대로 m개의 놀이기구 탑승
        for (int i = 0; i < m; i++) {
            // 각 놀이기구 당 t분 동안 탈 수 있는 인원 수 누적
            childNum += t/time[i];
        }

        return childNum;
    }
}

 

문제에서 입력 범위가 굉장히 큰 것을 보고 이분 탐색을 활용해서 해결하는 문제임은 캐치했는데, 무엇을 기준으로 이분 탐색을 해야 할지 굉장히 오랜 시간 고민했다. 처음엔 사람 수, 놀이 기구 수 등 여러 조건을 기준으로 삼아보려 했지만 적절한 기준이 아니라는 생각이 들었고, 결국 다른 분의 풀이를 참고하여 시간을 기준으로 잡아 문제를 해결할 수 있었다. 역시 이분 탐색은 탐색 대상을 적절하게 설정하는 것이 중요하다는 것을 다시 한번 깨달았다. 🤔💭

 

 

 

 

 

📃 reference

• https://loosie.tistory.com/713