[백준 1561]- 놀이 공원(C++)[골드2]

문제

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

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

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

입력

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

출력

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

 

🔎문제 해석

처음 풀이법으로 시간초과라는 결과를 선고받아서, 구글의 힘을 조금 빌려서,, 이분탐색을 사용하기로 했다.
이분탐색의 개념은 알지만 어떠한 경우 이분탐색을 사용하는지 여전히 헷갈리는 것 같다...
우선 해당 문제는 시간대를 이분탐색으로 탐색해서 해당 시간대에 몇 명이나 놀이기구에 탑승했는지를 구해서
start와 end범위를 조정하는 방식으로 문제를 풀었다.

N : 꼬맹이들 수, M : 놀이기구의 수이다.

우선 꼬맹이들의 수보다 놀이기구의 수가 많다면 당연스럽게도 마지막 꼬맹이가 타는 놀이기구의 번호는 꼬맹이의 번호와 같을 것이다.

즉 더는 검사할 필요성이 없다.

if(n<=m){
	cout<<n<<endl;
    return 0;
}

 

이제 우리가 주목해야 할 점은 꼬맹이들의 수가 놀이기구의 수보다 많을 때이다.

무작정 탐색해서 놀이기구의 시간을 한 칸씩 줄이기에는 매우 오랜 시간이 걸리기에, 이분탐색을 사용해야 한다.

 

N의 최대값은 2,000,000,000이고, 놀이기구의 운영시간은 최대 30분이다.

즉 만약 최~~~~대로 오래 걸리는 경우라면 N의 최댓값이 input으로 주어지고, 놀이기구의 개수는 1개이고, 그때의 운영시간이 30분일 때가 최고로 오래 걸리는 경우일 것이다.

하지만 최고의 범위는 그때그때 입력받은 놀이기구의 최댓값 * N이 최대 시간일 것이다.

 

이분탐색의 범위

start = 0, end = N * 운행시간의 최대값이 될 것입니다.

 

이분탐색을  통해서 우리는 해당시간대에 몇 명이나 놀이기구에 탑승할 수 있는지 구해야 합니다.

이분탐색은 아래의 과정으로 진행되며, start가 end이상이 될 경우 중단됩니다.

1. mid는 start와 end의 중간값이 될 것입니다. 
   1. start, end, mid는 모두 시간을 의미합니다.
2. mid 시간 동안 몇 명이나 놀이기구에 탑승했는지 구해야 합니다.
   1. 탑승인원이 n명보다 작다면 해당 시간대에는 전체 인원을 탑승시키기에 모자란 시간이므로, 탐색범위를 늘려줍니다.
      1. start = mid +1;
   2. 탑승인원이 n명보다 크다면 해당 시간대에는 전체 인원르 탑승시키에 충분한 시간입니다. 따라서 탐색범위를 줄여줍니다.
      1. end = mid;
      2. 그리고 모든 인원이 탑승한 시간인 mid를 최솟값으로 기록해줘야 합니다.

1번과 2번의 과정을 거치면 모든 인원이 탑승한 시간대를 알 수 있습니다.

• 우리가 원하는 것은 마지막 인원이 탑승한 놀이기구의 번호를 알고 싶기에,  time-1까지 몇 명이나 탑승했는지를 알아야 합니다.
• time-1까지 탑승한 인원을 알아낸 뒤에,
• time 시간대에서 탑승할 수 있는 놀이기구를 검사해서, 탑승할 수 있다면 탑승인원을 늘려주는 과정을 진행하다가 마지막 인원까지 도달했다면 그때의 놀이기구 번호를 출력해 주면 됩니다.

 

 

💻전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
long long n, m;
vector<int> play;
int main()
{
    cin >> n >> m;
    play.resize(m, 0);
    for (int i = 0; i < m; i++)
    {
        cin >> play[i]; // 운행시간을 뜻합니다.
    }
    if (n <=m)
    {
        cout << n << endl;
    }
    else
    {
        long long start = 0,mid=0 ,end = n*30; //최대 운행시간은 n명이고 1개의 놀이기구가 있을때 그 놀이기구 30분 일경우
        long long tt,time=n*30;
        while (1)
        {
            if(start>=end){
                break;
            }
            mid=(start+end)/2; //여기서 mid, start, end는 모두 시간을 의미함.
            tt = 0; //mid 시간 내에 놀이기구에 탑승할 수 있는 학생
            for(int i=0; i<m; i++){
                tt+=(mid/play[i])+1; 
                //+1을 해주는 이유는 예를 들어 5초시간대에는 운행시간이 3초인 놀이기구에는 2명이 탔는데 몫은 1이기에 1을 더해줌,
            }
            if(tt<n){ //전체 인원수보다 작다면.. 탐색하는 시간대를 늘려줘야함.
                start=mid+1;
            }
            else{ //이 경우는 모든 꼬맹이들을 다 태운 경우임.                
                time=min(time,mid); //다 태웠다면 더 낮은 시간대를 갱신함.
                end=mid;
            }
        }
        //time이 모든 아이들이 놀이기구를 탄 최소의 시간
        long long child=0;
        for(int i=0; i<m;i++){ //time-1까지 진행해서 탈 수 있는 아이들의 수를 계산함.
            child+=((time-1)/play[i])+1;
        }
        for(int i=0; i<m;i++){
            if(time%play[i]==0){ //time시간대에 탈 수 있는 놀이기구가 있다면 아이들을 탑승시킴.
                child++;
            }
            if(child==n){ //만약 아이들의 수가 n이라면 그때 마지막 탑승이기에 놀이기구의 번호를 출력함.
                cout<<i+1<<endl;
                return 0;
            }
        }
    }
}

 

😀느낀 점

• 풀이 접근 방식이 너무 어려워서 구글을 참고했다.
• 이분탐색이라는 풀이방식까지는 접근했는데, 시간대를 나눠서 해당 시간대에 탈 수 있는 사람의 수를 계산한다는 접근 방식이 조금 어려웠고, 이러한 방식이 아니면 시간초과가 났기에, 골드 2라는 난이도였던 것 같다.