YeJin's Footsteps

입국심사 본문

Computer Science & Engineering/알고리즘

입국심사

YeJinii 2021. 7. 9. 18:23

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/43238

 

코딩테스트 연습 - 입국심사

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한

programmers.co.kr

문제 풀이 코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

long long solution(int n, vector<int> times) {
    long long answer = 0;
    sort(times.begin(), times.end());
    
    long long start=1; long long end=(long long)times[times.size()-1]*n;
    long long mid=0;
    
    answer=end;
    
    while(start<=end){
        long long cnt=0;
        mid=(start+end)/2;
        for(long long i=0; i<times.size(); i++){
            cnt+=mid/times[i];
        }
        
        if(cnt<n){
            start=mid+1;
        }
        else{
            answer=mid;
            end=mid-1;
        }
        //cout<<cnt<<" "<<mid<<endl;
    }
    return answer;
}

어려웠던점

1. 예제 문제의 경우 cnt=n 가 28,29분 둘다 가능하기 때문에

가능한 시간중 최솟값을 찾는것이 관건이였다.

2. times배열도 캐스팅을 해줘야 하는지는... 오버플로우 화난다 ㅋㅋ

'Computer Science & Engineering > 알고리즘' 카테고리의 다른 글

짝지어 제거하기  (0) 2021.07.17
크레인 인형 뽑기 게임  (0) 2021.07.17
순위  (0) 2021.07.09
가장 먼 노드  (0) 2021.07.08
네트워크  (0) 2021.07.08
Comments