문제 탐색하기

입력 자료 정리

1. n은 아이들의 수, m은 놀이기구의 개수다
2. 이어서 들어오는 m개의 값은 각 놀이기구를 이용하는데 걸리는 시간이다

해결방법 추론

1. 일단 n과 m의 입력값을 보면 브루트포스로는 절대 해결할 수 없다는 것을 알 수 있다
2. 또한 n의 최대 크기가 20^9이므로 단순한 탐색이나 dp만으로도 해결하기 어렵다는 것을 알 수 있다
3. 이 정도 크기의 입력값이면 이분탐색을 이용해야할 것이다
4. 그렇다면 이분탐색의 대상은 무엇으로 해야할까?
5. n이 아이들의 수니까 아이들의 수를 대상으로 해야할까?
6. 하지만 5번으로 하기에는 마지막 아이가 놀이기구에 타는 번호를 구할 수 없다
7. 아이들의 수는 불가능하고... 시간을 대상으로 이분탐색의 대상으로 해보면 어떨까?
8. 특정 시간에 각 놀이기구별로 이용을 완료하는 아이들의 수를 구한다음 최대한 n에 가깝게 한다면?
9. 8번대로 한다면 n명의 아이가 모두 놀이기구를 이용 완료하는 시간을 구할 수 있을 것이다!
10. 하지만 조금 더 생각해야할 것이, n명을 모두 태우는 시간을 구한다고 해서 마지막 아이가 타는 놀이기구의 번호는 구할 수 없다
11. 그렇다면 시간도 대상이 될 수 없는 것일까? 하지만 시간마저 대상에서 지워버리면 더이상 이분탐색의 대상으로 할 것이 없어진다
12. 그럼 어떻게 해야할까? 떠올린 방법은 구한 시간의 1분전 이용완료하는 아이들 수를 구한 뒤,
    모든 놀이기구를 탐색하면서 현재 시간대에 태울 수 있는 놀이기구의 개수를 파악하는 것이다
13. 이렇게 하나씩 개수를 늘리면서 n이 되는 지점을 마지막 아이가 타게되는 놀이기구의 번호라고 판단하면 될 것이다!
14. 추가로 한가지 예외를 생각해야한다. n이 m이하인 경우 0초에 모두 아이를 태울 수 있으므로 그냥 n을 출력하면 된다!

시간복잡도 계산

1. 먼저 이분탐색의 범위를 계산해야한다. 최소는 1, 최대는 n x 30이 될 것이다
2. 이어서 이분탐색할때마다 m만큼의 연산이 발생한다.
3. 이것을 모두 조합하면 O(m x logn)의 시간복잡도가 발생한다
4. m은 10^4이고, 6 x 10^10이므로 대략 10,000 x 10의 크기로 계산되며,
   시간제한인 2초 안에 문제를 해결할 수 있다!

코드 설계하기

입력값 상태 관리

1. 이번 문제는 조금 특이하게도 n은 long 타입의 변수로 입력받아야한다
2. m은 그대로 int형 변수에 입력받으면 된다
3. m크기의 int형 1차원 배열에 각 놀이기구의 운행시간을 저장한다

구현 코드 설계

1. n이 m보다 작으면 n을 출력하도록 하며, 아닌 경우 이분 탐색을 하도록 구현한다
2. 먼저 n명에 가깝게 태울 수 있는 시간을 구하기 위해 이분탐색을 진행한다
3. left는 최소시간인 1로 초기화하며, right는 최대시간인 n x 30로 초기화한다
4. mid시간에 놀이기구별로 태울 수 있는 인원을 구하기 위해 coutn 변수를 선언한다
5. 이때 0초에 모든 놀이기구를 운행할 수 있으므로 count변수를 m으로 초기화한다
6. count가 n보다 작으면 left를 조절하고 반대는 right를 조절한다.
7. right를 조절할 때는 정답 시간으로 선정 가능하므로 nCount를 mid로 초기화한다
8. 이분탐색 종료 후, 해당 시간의 1분전을 구하기 위해 mCount 변수를 선언한다
9. 똑같이 해당 시간에 태울 수 있는 아이 수를 구한다음 ans 변수에 저장한다
10. m만큼 순회하면서 nCount 시간에 태울 수 있는 놀이기구를 파악한다.
    이때 모듈러 연산 결과가 0이면 해당 시간에 태울 수 있다. 따라서 해당 경우에 ans를 늘려준다

출력값 설계

1. ans가 n과 같으면 마지막 아이가 타는 놀이기구이므로, 0부터 시작한 i에 1을 더한 값을 출력한다. 이후 반복문을 break로 탈출하면 정답이 된다!

정답 코드

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

public class Main {


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long n = Long.parseLong(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[] arr = new int[m];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        if(n <= m){
            bw.write(n+"");
        }else{
            long left = 1;
            long right = n*30;
            long nCount = left;
            while(left <= right){
                long mid = (left + right) / 2;
                long count = m;
                for (int i = 0; i < m; i++) {
                    count += mid / arr[i];
                }
                if(count < n){
                    left = mid + 1;
                }else{
                    right = mid - 1;
                    nCount = mid;
                }
            }

            long nMCount = nCount-1;
            long count = m;
            for (int i = 0; i < m; i++) {
                count += nMCount / arr[i];
            }
            long ans = count;

            for (int i = 0; i < m; i++) {
                if(nCount % arr[i] == 0){
                    ans++;
                }
                if(ans == n){
                    bw.write(i+1+"");
                    break;
                }
            }
        }

        br.close();
        bw.close();
    }

}

문제 링크

1561번 - 놀이 공원