본문 바로가기
Algorithm/이분탐색

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

by 젊은오리 2023. 4. 6.
728x90

 

문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/43238

KEY

  • 시간을 기준으로 이분탐색한다는 방법 자체를 떠올리기가 어려운 문제다.
  • 1분~가장 오래 걸리는 시간 까지 이분탐색으로 시간을 탐색하면서, 모든 사람이 심사를 받을 수 있는 시간 중 가장 짧은 시간대를 찾으면 된다.
  • 시간을 심사대의 시간으로 나누어 더함으로써 완료할 수 있는 사람 수(cnt)를 센다. 가령 심사대는 7, 10분 두개가 있고, 지금 시간이 30분이라고 할 때, 완료할 수 있는 사람 수는 30/7 + 30/10 = 6이다.
  • 자료형에 조심하자.

 

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#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 end = (long long)times.back() * n;
    long long start = 1;
    
    while(start <= end){
        long long mid = (start + end/ 2;
        long long cnt = 0;
        for(int i=0;i<times.size();i++){
            cnt += mid / times[i];
        }
        
        if(cnt >= n){
            end = mid - 1;
            answer = mid;              
        }else
            start = mid + 1;
            
        }
        
    }
    return answer;
}
cs
728x90

'Algorithm > 이분탐색' 카테고리의 다른 글

[백준] 1920 수찾기 c++  (0) 2023.03.31
[백준] 1654 랜선 자르기 c++  (0) 2023.02.25

댓글