[프로그래머스/C++] 입국심사

 

 

문제

문제 설명

 

 

 

 

풀이

 

[문제 풀이]

 

처음에 문제를 봤을 때, 범위가 말이 안되기 때문에 times의 최소공배수를 구해서 나누어야하나? 생각이 들었다.

그런데 아무리 봐도 times의 범위도 매우 길 뿐더러 나눠도 해결이 안될 것이라고 생각해 다른 방법을 생각해봤다.

그 다음으로는 최소힙을 만들고 거기에 특정 심사가 만료되면 몇분이 되는지를 저장하는 방식을 생각했다. 구현만 하면 가능하겠지만, 1,000,000,000번 힙에 삽입 삭제를 하면 시간초과가 될 게 분명해서 이 방법도 넘겼다.

 

이렇게 힙을 생각하다보니 특정 사람의 심사가 끝나는 시간을 한명씩 넘겨가면서 구하는 것보다 반대로 특정 시간에 몇명을 심사할 수 있는지를 계산하면 되겠다는 생각이 들었다.

 

그래서 나눗셈을 이용해 특정 분이 지나면 몇명을 심사할 수 있는지를 이분탐색으로 찾아가며 가장 시간이 짧은 분을 구하도록 코드를 짰다.

 

​

[아이디어 정리]

1. 특정 분을 정하고 그 시간에 몇명을 심사할 수 있는지를 계산한다.​
2. 몇 명을 심사할 수 있는지는 [minuite] / times[i] 의 총합으로 구할 수 있다.
3. 만약 심사 가능한 인원이 심사 대기 인원보다 많으면 ed를 mid-1로 하고 다시 탐색한다.
4. 만약 심사 가능한 인원이 심사 대기 인원보다 적으면 st를 mid+1로 하고 다시 탐색한다.
5. st가 ed보다 커지면 그때, st를 return한다.

 

 

Code

 

 

#include <string>
#include <vector>
using namespace std;

long long solution(int n, vector<int> times) {
    long long answer = 0;
    long long st=1,mid, cnt;
    long long ed=1000000000000000000; // 최대값
    // 이분 탐색으로 특정 분에 완료가 되는지를 검사하면 됨    
    while(st<=ed)
    {
        mid=(st+ed)/2;
        cnt=0;   
        for (int i=0; i<times.size(); i++)
        {
            cnt+=mid/times[i];
            if (cnt>n)
            {
                ed=mid-1;
                break;
            }
        }
        if (cnt>=n)
        {
            ed=mid-1;
        }
        else
        {
            st=mid+1;
        }
    }
    return st;
}

 

---

 

 

이런 문제는 아이디어가 떠오르면 진짜 쉬운데 안떠오르면 도저히 생각나지 않는 문제...

 

 

프로그래머스