[ Baekjoon - 10/31 ] - 1561번: 놀이 공원

• 문제 링크 : https://www.acmicpc.net/problem/1561

1561번: 놀이 공원

 

• 소요 시간 : 2시간

놀이 공원 

한국어   

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

8880

2265

1582

24.835%

문제

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

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

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

입력

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

출력

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

예제 입력 1 복사

3 5
7 8 9 7 8

예제 출력 1 복사

3

예제 입력 2 복사

7 2
3 2

예제 출력 2 복사

2

예제 입력 3 복사

22 5
1 2 3 4 5

예제 출력 3 복사

4

 

1. 문제를 읽고 이해하기
   • 제한
     • 시간 : 2초
     • 메모리 : 128MB
   • 문제
     
     • N명의 아이들(1≤N≤2,000,000,000), 1인승 놀이기구 수 M(1≤M≤10,000)
     • 같은 시간에 놀이기구가 비어있으면, 작은번호의 놀이기구부터 탑승시키고
       그게 아닌 경우에는 빈 놀이기구에 탑승시킨다.
     • 이때 마지막 인원이 타게 될 놀이기구의 번호를 출력하는 문제
   • 이해
     • 단순하게 생각하면 금방 풀릴문제같지만 조건이 굉장하기때문에.. 문제접근에 꽤 많은 생각을 해야했던 문제였다.
2. 문제를 익숙한 용어로 재정의와 추상화

   • 

   • 시간 테이블을 그려보며 규칙을 파악하려 했다.
3. 문제를 어떻게 해결할 것인가
   • 1st 접근 - 정렬)
     • 기구의 시작시간과 운영시간을 보관하는 리스트에서, 시작시간 순으로 오름차순하고, 시작시간이 같다면 해당 놀이기구의 번호로 오름차순으로 정렬하면 문제 조건에 맞는 정답을 도출할 수 있을거라 생각하였다.
     • 그렇지만, 단순히 하나의 인자만으로 정렬하는것또한 NlogN인데 N이 2억까지가는 문제이므로 시간초과도 당연하고 메모리도 128은 가뿐히 넘길 수 있기때문에 적합하지 않은 방법이다...
     • 제대로 검증을 안하고 이 방법을 시도했어서 약 40분정도를 그냥 날렸던것 같다..큐큐ㅠ
   • 2nd 접근 - 이분탐색)
     • 아무리 고민해봐도 도저히 접근방법이 떠오르지 않아서 알고리즘 종류를 봤는데 이분탐색과 매개변수탐색이었다.
     • 이분탐색으로 시간복잡도 logN의 이득을 가져가기 위해서는 단 한번만의 탐색으로 원하는값을 도출할 수 있어야하는데.. 어떤 값을 가져와야 결과도출을 위해 적은 연산을 할수있을지 오래 고민을 했다..
     • 생각하던중 N명의 모든 아이들이 탈 수 있는 분(시간)을 가져올 수 있다면, 해당 시간의 몇번째 놀이기구 차례인지 알수있고 즉 원하는 값을 얻을 수있을거라 생각했다.
     • 어떻게 시간을 이분탐색으로 추출할 수 있을지 생각해보았는데, 처음엔 각각 운행시간만큼의 단위로만 생각했다면, 이번에는 1분단위로 현황을 표로 만들어 보기로 했다.

     • 

     • 표의 행은 1분단위의 시간, 열은 M개의 기구의 번호로 두고, 맵의 숫자는 N명의 아이들중 몇번째 아이인지를 넣었다.
     • 이렇게 표를 만들었을때, 행의 소요시간을 각 운행시간으로 나누면 사람을 몇번 탑승시켰는지를 알아낼 수 있으므로 구해낼 수 있을거라 생각했다!
     • 이제 이분탐색의 조건을 생각해야 했는데, 지금 분(시간)까지 태운 사람의 수가 N명보다 작다면 left 증가, 크다면 right감소 하는 방식으로 탐색할 수 있을거라 생각했고 바로 코드로 작성해 보았다.
4. 위 계획을 검증
   • 이분탐색은 logN의 시간복잡도이고, 시간을 가져오기위해 사용한 것이므로, 상수의 시간복잡도로 해당 시간에 따른 어느 놀이기구를 탔는지 구할 수 있기때문에 시간은 충분하다.
   • 메모리또한, 꼭 넣어야하는 입력값정도로 구성되어있으므로 가능하다고 생각한다.
5. 계획 수행 (실제코드 작성)
   1. Java 11

      • import java.io.*;
        import java.util.*;
        
        public class Main {
            static int M,max;
            static long N,t;
            static int[] time;
        
            public static void main(String[] args) throws Exception {
                //System.setIn(new FileInputStream("src/input.txt"));
        
                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                StringTokenizer st = new StringTokenizer(br.readLine());
                N = Long.parseLong(st.nextToken());
                M = Integer.parseInt(st.nextToken());
        
                time = new int[M + 1];
                st = new StringTokenizer(br.readLine());
                for (int m = 1; m <= M; m++) {
                    time[m] = Integer.parseInt(st.nextToken());
                    max = Math.max(max, time[m]);
                }
        
                if (N <= M) {
                    System.out.println(N);
                } else {
                    // N명이 전부 탈 수 있는 시간
                    t = binSearch(0, (N / M) * max);
        
                    long cnt = M;
                    // N명이 전부 탈 수 있는 시간의 1분 전 현황 구하고
                    for (int m = 1; m <= M; m++)
                        cnt += (t - 1) / time[m];
        
        
                    for (int m = 1; m <= M; m++) {
                        // 언제 승객을 태웠는지를 체크하면 원하는 사람이 탈때
                        if (t % time[m] == 0)
                            cnt++;
        
                        // cnt 가 N과 같아지므로 해당값 출력
                        if (cnt == N) {
                            System.out.println(m);
                            return;
                        }
                    }
                }
            }
        
            public static long binSearch(long left, long right) {
                long l = left;
                long r = right;
        
                do {
                    long pc = (l + r) / 2;
                    // 가장 처음 빈 M개의 놀이기구에 모두가 탑승
                    long sum = M;
                    for (int m = 1; m <= M; m++) {
                        // n분(시간) / m => 해당 놀이기구가 1 ~ n 분까지 태운 사람 수
                        sum += pc / time[m];
                    }
        
                    if (sum < N)
                        l = pc + 1;
                    else
                        r = pc - 1;
                } while (l <= r);
        
                return l;
            }
        }

   2. Python 3

      • import sys
        #sys.stdin = open("input.txt")
        input = sys.stdin.readline
        
        def binarySearch(left, right):
            l = left
            r = right
        
            while l<=r:
                pc = int((l+r)/2)
                # 가장 처음 빈 M개의 놀이기구에 모두가 탑승
                sum = M
                for m in range(1,M+1):
                    # n분(시간) / m => 해당 놀이기구가 1 ~ n 분까지 태운 사람 수
                    sum += int(pc / time[m])
        
                if sum<N:
                    l = pc+1
                else:
                    r = pc-1
        
            return l
        
        if __name__ == '__main__':
            N, M = map(int, input().split())
            time = [0]+list(map(int, input().split()))
            maxV = max(time)
        
            if N<=M:
                print(N)
            else:
                # N명이 전부 탈 수 있는 시간
                t = binarySearch(0, (N/M)*maxV)
                cnt = M
                # N명이 전부 탈 수 있는 시간의 1분 전 현황 구하고
                for m in range(1, M+1):
                    cnt += int((t-1) / time[m])
        
                for m in range(1, M+1):
                    # 언제 승객을 태웠는지를 체크하면 원하는 사람이 탈때
                    if int(t % time[m]) == 0:
                        cnt+=1
        
                    # cnt 가 N과 같아지므로 해당값 출력
                    if cnt==N:
                        print(m)
                        break

 

 

• 결과

• Java11
  • 메모리초과 - 첫번째 접근대로 했다가 얻은 결과
  • 틀렸습니다, 컴파일에러 - int욕심부리다가 얻은 결과... long으로 바꿔주니 맞았습니다를 얻을 수 있었다.
• Python 3
  • 런타임에러 - 입출력 편하게 하기위한 코드를 주석처리하지 않고 제출해서 얻은 결과