22.05.16. 풀었던 문제들

1. 입국심사

binary search로 풀 수 있는 문제. 다만 형변환을 조심했어야 했다... 이것 때문에 시간을 날림.

// 입국심사

using namespace std;

typedef long long ll;

ll isEnough(vector<int> times, ll t){
    ll cnt = 0;
    for(int i : times){
        cnt += (ll)t/(ll)i;
    }
    return cnt;
}

long long solution(int n, vector<int> times) {
    long long answer = 0;
    ll l = 1L, r = (ll)(*max_element(times.begin(), times.end())) * n, mid;
    
    while(l < r){
        mid = (l+r)/2;
        ll pass_num = isEnough(times, mid);
        if(isEnough(times, mid) < n) l = mid+1;
        else{
            r = mid;
        }
    }
    
    return l;
}

 

2. 가장 먼 노드

벨만-포드의 경우 O(VE)에 풀 수 있지만 BFS 이용 시 O(V + E)만에 풀 수 있다.