2025/02/10 백준 1561 놀이공원

난이도: G1

알고리즘: 이분탐색

 

https://www.acmicpc.net/problem/1561

 

1. 문제 탐색

 

제한 시간: 2초, 메모리 제한: 128MB

 

N의 범위가 최대 2억, M의 범위가 최대 10000이므로 O(N)은 시간 초과가 발생한다.

이분 탐색으로 풀어서 시간을 단축하자.

그리고, 놀이기구 순서보다는 X초에 몇 명이 놀이기구를 타는지 시간 중심으로 생각해보자.

 

2. 코드 설계하기

0초에는 빈 놀이기구에 모두 탑승한다. 

-> 0초: m명

 

그리고 x초에는 x/m[i]의 합 만큼 탑승한다.

 

n명의 아이들이 모두 탑승하는 x분를 구해보자. - 이분탐색으로

int low = 0(초), int high = n*30(초), int mid = (low+high)/2

 

target초에 탑승인원이 총 몇 명인지 계산하고 n보다 작으면, low=mid+1로 설정하고

n보다 크거나 같으면, high = mid으로 설정한다.

-> 결과로 나온 high가 n명을 태울 수 있는 최소 시간이다.

 

마지막 아이가 탄 놀이기구 번호를 구하기 위해

high-1일 때의 몇 명의 아이가 남는지 구하고, 1분이 지난 후에 어떤 상황이 벌어지는지 확인한다.

(high일 때는 이미 모든 아이들이 탔기 때문에 마지막 아이가 몇 번 놀이기구를 탔는지 모른다.)

high초에서 타는 아이들은 high%m[i]==0인 인덱스i 놀이기구에 탄다.

 

거의 모든 변수를 long long으로 해놓고 코드를 작성해야한다.

int변수로 설정하고 이후에 long long으로 자료형 변환을 하려고 하면, 실수가 발생하여 연산 과정에서 자동으로 int로 변환되는 경우가 생길 수 있다. 

 

3. 시도회차별 수정 사항

 

n<m인 경우를 분기처리해야한다.

n<m인 경우 모든 아이들을 태울 때 0분 걸리기 때문에 모든 놀이기구가 빈 상황에서 따져봐야한다. - beforeTime을 따로 구할 필요가 없다.

따라서 time이 0보다 큰 경우에만 beforeTime을 따로 구해줘야한다.

 

4. 정답코드

#include <iostream>
#include <vector>

using namespace std;

long long calcNum(long long time, vector<long long> &arr, long long m)
{
    long long cnt = m; //0초에 빈 놀이기구 m개에 다 탐.
    
    for(int i=0; i<m; i++)
    {
        cnt += time/arr[i];
    }

    return cnt;
}

long long calcMinTime(long long n, vector<long long> &arr)
{
    long long low = 0;
    long long high = n*30;
    long long cnt = 0;

    while(low<high)
    {
        long long mid = (low+high)/2;
        cnt = calcNum(mid, arr, arr.size());

        if(cnt<n)
        {
            low = mid+1;
        }
        else
        {
            high = mid;
        }
    }

    return high;    
}

int main()
{
    long long n, m, ans;

    cin>>n>>m;

    vector<long long> arr(m, 0);

    for(int i=0; i<m; i++)
    {
        cin>>arr[i];
    }

    long long time = calcMinTime(n, arr);
    long long beforeNum = 0; //time-1분일때 놀이기구 탄 아이들 수
    if(time>0)
    {
        beforeNum = calcNum(time-1, arr, m); 
    }

    for(int i=0; i<m; i++)
    {
        if(time%arr[i]==0) //time일 때 놀이기구가 비는 경우 = 아이가 타는 경우
        {
            beforeNum += 1;
        }

        if(beforeNum == n)
        {
            ans = i+1;
            break;
        }
    }

    cout<<ans;

}