프로그래머스 - 금과 은 운반하기

프로그래머스 - 금과 은 운반하기

문제를 받자마자 어떻게풀지? 라는 생각부터 들어서 공부부터 했다;
공부하다보니 해당 문제가 Binary Search 문제라는 것을 깨달았고, 대충 감이 와서 그 뒤로는 금방 풀었다.

참고 자료 : 이분탐색 - Parmetric Search

end를 충분히 큰 숫자로 두고, start는 0으로 설정하고 mid는 (start + end) / 2로 설정한다.
그 후 다른 Binary Search처럼 서치를 시작하면 된다.

mid가 의미하는 것은 time이다. 만약 500이라면 500초 순간에서의 금 운반량과 은 운반량을 계산하면 된다.

운반 횟수를 결정할 때 체크해야되는 것은 트럭이 왔다갔다 하는 것이다.
예를 들어, 트럭이 가는데 10초 걸린다고 가정하면 올 때도 10초이기 때문에 10~29초에는 운반 횟수는 1회이다.

그 후 남은 금/은 의 보유량을 고려해서 운반량을 체크해주고, 그 것이 문제에서 주어진 a, b를 넘기는지를 체크해준다.

추가적으로 나는 풀이 과정에서 w[i]를 따로 고려하여서 금과 은을 옮기지 않았기 때문에 그 총량을 따로 계산해주어야 했다.

#include <string>
#include <vector>

using namespace std;

long long solution(int a, int b, vector<int> g, vector<int> s, vector<int> w, vector<int> t) {
    long long answer = 4 * 1e6 * 1e10;
    long long start = 0;
    long long end =  4 * 1e6 * 1e10;
    int num_of_truck = g.size();

    while(start <= end) {
        long long mid = (start + end) / 2;
        long long gold_carry = 0;
        long long silver_carry = 0;
        long long total_carry = 0;
        for(long long i=0;i<num_of_truck;i++) {
            long long div = (long long)mid / t[i];
            long long move = div % 2 ? (div + 1) / 2 : div / 2;
                        
            if(g[i] > move * w[i]) 
                gold_carry += move * w[i];
            else 
                gold_carry += g[i];
            
            if(s[i] > move * w[i]) 
                silver_carry += move * w[i];
            else 
                silver_carry += s[i];
            
            if(g[i] + s[i] > move * w[i]) 
                total_carry += move * w[i];
            else 
                total_carry += (g[i] + s[i]);
        }
        
        // Total Carry가 없으면 TC 1같은 경우 30으로 답이 나옴.
        // Silver + Gold가 W[i]를 넘기는지 따로 체크를 안해주고, 그냥 옮겨진 총량이 a + b를 넘기는지만 체크.
        if(gold_carry >= a && silver_carry >= b && total_carry >= a + b) {
            if(answer > mid) 
                answer = mid;
            end = mid - 1;
        } else 
            start = mid + 1;
    }
    
    return answer;
}