백준 1561번 놀이 공원

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

문제를 'x분에 몇 번째 학생부터 몇 번째 학생이 놀이기구를 타는가?'로 바꾸어야했던 문제였습니다.

알고리즘은 아래와 같습니다.

1. 놀이기구 수보다 아이들의 수가 적으면 아이들의 수를 출력해주면 됩니다.

2. 이분 탐색을 통해 마지막 아이가 탑승한 시간을 찾습니다.

3. (2번에서 구한 시간 - 1)분까지 몇 명의 아이들이 탑승했는지 탐색합니다.

4. 3번을 토대로 2번에서 구한 시간에 마지막으로 탑승하는 아이가 타는 놀이기구를 찾으면 됩니다.

#include <iostream>

#include <algorithm>

using namespace std;

 

const int MAX = 10000;

 

int N, M;

int ride[MAX];

 

long long binarySearch(void)

{

        long long low = 0, high = 2000000000LL * 30LL;

        long long result = -1;

        while (low <= high)

        {

                 long long mid = (low + high) / 2;

                 long long children = M;

                 for (int i = 0; i < M; i++)

                         children += mid / ride[i];

 

                 if (children >= N)

                 {

                         result = mid;

                         high = mid - 1;

                 }

                 else

                         low = mid + 1;

        }

 

        return result;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> N >> M;

       

        for (int i = 0; i < M; i++)

                 cin >> ride[i];

 

        //놀이기구 수보다 아이들의 수가 적을 경우

        if (N <= M)

        {

                 cout << N << "\n";

                 return 0;

        }

 

        //마지막 아이가 탑승한 시간을 찾는다

        long long time = binarySearch();

        long long children = M;

        //(time - 1)까지 탑승한 아이들을 전부 더한다

        for (int i = 0; i < M; i++)

                 children += (time - 1) / ride[i];

 

        //time에 탑승한 아이를 확인한다

        for (int i = 0; i < M; i++)

        {

                 if (!(time % ride[i]))

                         children++;

 

                 if (children == N)

                 {

                         cout << i + 1 << "\n";

                         break;

                 }

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~