[백준] 1561번 놀이공원

1561 놀이공원

문제

---

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

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

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

입력

---

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

출력

---

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

---

풀이)

binary search문제. 상당히 고민했던 문제이다.

어떻게 돌아가는지 알기 위해, 아래처럼 표를 작성했었는데 그것이 문제 풀이에 큰 도움이 되었다.

(예시입력 1, 아이들이 22명일때에 대한 표)

표 안에는 n번째 아이 번호 삽입

      1번놀이기구 2번놀이기구 3번놀이기구 4번놀이기구 5번놀이기구

시간(분)＼운영시간	1	2	3	4	5
0	1	2	3	4	5
1	6
2	7	8
3	9		10
4	11	12		13
5	14				15
6	16	17	18
7	19
8	20	21		22

표를 기반으로 생각해낸 풀이 과정은 이렇다.

1. 시간을 binary search로 정해준다.

2. 시간내에 몇 명이 놀이기구를 탈 수 있는지 확인한다.

3. 인원보다 많이 탈 수 있다면 시간을 감소시키고, 

    적게 탄다면 시간을 늘린다.

위의 1,2,3을 반복하여 n명이 모두 다 놀이기구를 탈 수 있는 최소시간 minute를 구한다.

4. 최소시간을 구했으므로 minute - 1분째에는 몇 명이 탈 수 있는지 확인한다.

5. 낮은 번호를 가진 놀이기구부터, minute때에 탈 수 있었는지 확인하면서

   인원이 딱 n명이 될때 어떤 놀이기구 번호인지 출력한다.

주의할점

0분째에는 놀이기구 개수가 m개 이면, m명이 탈 수 있다.

따라서 인원이 m보다 작으면 위의 과정은 필요가 없고, 바로 놀이기구 번호를 출력하면된다.

//0분째 확인
if (n <= m) {
    printf("%d", n);
    return 0;
}

처음에 위의 과정을 생각못해서 틀렸었다.

위의 과정을 안할경우 풀이 4번에서 오류가 나기때문이다. (minute = 0이니깐 minute - 1 = -1) 

코드)

#include <stdio.h>
#include <algorithm>
using namespace std;
 
int n, m;
long long time[10000];
 
int main() {
    scanf("%d %d", &n, &m);
    long long val = 0;
 
    for (int i = 0; i < m; i++) {
        scanf("%lld", &time[i]);
        val = max(val, time[i]);
    }
 
    //0분째 확인
    if (n <= m) {
        printf("%d", n);
        return 0;
    }
 
    long long start = 1;
    long long end = val *n;
    long long minute = val * n;
    while (end > start)
    {
        long long mid = (start + end) / 2;
        long long temp = 0;
 
        for (int i = 0; i < m; i++) {
            temp += (mid / time[i])+1;
        }
        if (temp < n) {
            start = mid + 1;
        }
        else {
            minute = min(minute, mid); //아이들을 다 태우는 최소시간
            end = mid;
        }
    }
 
    long long temp = 0;
    //minute -1 분에는 몇명까지 탈 수 있는지
    for (int i = 0; i < m; i++) {
        temp += ((minute - 1) / time[i])+1;
    }
    for (int i = 0; i < m; i++) {
        //딱 mimute때에 탈 수 있는 놀이기구였다면
        if (minute  % time[i] == 0) {
            temp += 1;
            //마지막 아이가 탄 놀이기구였다면
            if (temp == n) {
                printf("%d", i + 1);
                return 0;
            }
        }
    }
 
    return 0;
}

결과)