백준 1561번 놀이 공원

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

1561번: 놀이 공원

 

문제

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

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

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

 

입력

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

 

출력

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

 

풀이

처음에 풀 때 범위는 어느정도 파악했는데, 범위에 따라 몇 명을 태울 수 있는지 계산이 안돼서 못 풀고

백준님 설명을 듣고 푼 문제이다. ㅠㅠ

문제는 이렇다. n명의 아이들이 있고, 총 M개의 (운행시간이 제각각이고 번호가 다른) 놀이기구가 있는데,

마지막 아이가 놀이기구에 탑승하는 놀이기구의 번호를 구하는 문제이다.

놀이기구의 규칙은

• 우선 모든 놀이기구는 처음에 비어있다.
• 어떤 놀이기구에 운행 시간이 지나면 즉시 바로 앞에 있는 아이가 탄다.
• 놀이기구들이 동시에 비게 되면 더 작은 놀이기구 우선으로 탑승한다.

문제 입력 조건에 N은 20억이기 때문에 N이 범위라고 생각될 수 있지만, N은 범위에 따른 조건이라고 봐야한다.

왜냐하면 놀이기구들이 동시에 빌 수 있기 때문이다.

그렇다면 이 문제는 K분에 총 몇 명까지 놀이기구를 탈 수 있는가? 로 생각할 수 있다.

 

그럼 바로 시간의 범위를 정해보자.

만약 놀이기구 운행시간이 전부 10만이고, 20억명이 있을 때,

시간의 최대 범위는 대충 높게 잡아 10억 x 10만 정도면 충분할 것이다.

최소는 아이들이 바로 타는 경우, 즉 0분이며 이때 마지막 아이가 타게되는 놀이기구의 번호는 N번이 되겠다.

따라서 범위는

• left(최소값) : 0
• right(최대값) : 10억 x 10만
• mid(중간 값) : (left + right) / 2

이며, 이제 중요한 건 k분까지 몇 명이 놀이기구를 이용했고, 정확히 k분에는 몇 명이 놀이기구를 탈 수 있는지 계산해야한다.

따라서 밑의 표를 그려보았다.

운행시간/시간	0	1	2	3	4	5
1	1	6	7	9	11	14
2	2		8		12
3	3			10
4	4				13
5	5					15

이 표에서 3가지 사실을 파악할 수 있다.

• 0분에는 M만큼의 사람이 탄다.
• A 놀이기구가 K분까지 몇 명을 태우는가? K / (A의 운행시간) 
• K분에 몇 개의 놀이기구가 운행 가능한가? 각각의 놀이기구 운행시간 % K == 0 일 때마다 카운트 

이 사실을 바탕으로 mid시간을 대입했을 때 mid시간 전까지 몇명이 탔는가? 를 계산하여

mid시간 <= N <= mid+1시간 인 mid를 구하고,

mid시간에 몇 개의 놀이기구가 운행가능하느냐에 따라서,

N - (mid시간 전까지 탄 명 수) 가 0이 될 때 까지 놀이기구의 번호를 구하면 정답을 구할 수 있다.

 

소스 코드

#define MAX 1000000000LL * 100000LL
#include <iostream>
using namespace std;
int a[10000];
int p, n;
int main()
{
    scanf("%d%d", &p, &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    if (p <= n) {
        printf("%d\n", p);
        return 0;
    }
    long long left = 0;
    long long right = MAX;
    while (left <= right) {
        long long mid = (left + right) / 2;
        long long begin, end; 
        //begin,end : begin시간이 시작하기전과 끝날때까지 몇명탔는가?
        begin = end = 0;
        end = n; //처음에 바로 n명이 타니까
        for (int i = 0; i < n; i++) {
            end += mid / a[i];
        }
        begin = end;
        for (int i = 0; i < n; i++) { //mid시간에 탄 친구들은 빼준다
            if (mid % a[i] == 0) begin -= 1;
        }
        begin += 1;
        if (p < begin) { //덜 탄경우
            right = mid - 1;
        }
        else if (p > end) { //너무 많이 탄 경우
            left = mid + 1;
        }
        else { //p가 begin과 end 사이 범위에 들어갈 때(정답 범위 내)
            for (int i = 0; i < n; i++) {
                if (mid % a[i] == 0) { //mid시간에 a[i]가 쉬는경우
                    if (p == begin) { //p가 바로 begin인경우
                        printf("%d\n", i + 1);
                        return 0;
                    }
                    begin++; //begin이 end까지 갈때까지 ㄱㄱ
                }
            }
        }
    }
    return 0;
}

개발환경 : Visual Studio 2019

지적, 조언 언제든지 환영입니다~~