[ 프로그래머스 C++ ] 금과 은 운반하기 lv3

해설

이분탐색으로 해결해야하는 문제다. 

자원 * 시간 / 트럭에 싣고 갈 무게

로 이분탐색을 해주면 된다.

 

나는 최댓값 설정을 LLONG_MAX 로 했는데 자꾸 실패가 떴다..

최댓값 설정은

1. 자원 : 금과 은의 최대 요구량 -> 10e9 * 2
2. 시간 : 왕복 시간으로 계산 -> 10e5 * 2
3. 트럭에 싣고 갈 무게 = 1 으로 해서 구해주면 된다.

따라서 최대값은 10e5 * 4 * 10e9 으로 설정해주면 된다.

---

문제 설명

어느 왕국에 하나 이상의 도시들이 있습니다. 왕국의 왕은 새 도시를 짓기로 결정하였습니다. 해당 도시를 짓기 위해서는 도시를 짓는 장소에 금 a kg과 은 b kg이 전달되어야 합니다.

각 도시에는 번호가 매겨져 있는데, i번 도시에는 금 g[i] kg, 은 s[i] kg, 그리고 트럭 한 대가 있습니다. i번 도시의 트럭은 오직 새 도시를 짓는 건설 장소와 i번 도시만을 왕복할 수 있으며, 편도로 이동하는 데 t[i] 시간이 걸리고, 최대 w[i] kg 광물을 운반할 수 있습니다. (광물은 금과 은입니다. 즉, 금과 은을 동시에 운반할 수 있습니다.) 모든 트럭은 같은 도로를 여러 번 왕복할 수 있으며 연료는 무한대라고 가정합니다.

정수 a, b와 정수 배열 g, s, w, t가 매개변수로 주어집니다. 주어진 정보를 바탕으로 각 도시의 트럭을 최적으로 운행했을 때, 새로운 도시를 건설하기 위해 금 a kg과 은 b kg을 전달할 수 있는 가장 빠른 시간을 구해 return 하도록 solution 함수를 완성해주세요.

---

코드

#include <string>
#include <vector>
#include <limits.h>

using namespace std;

bool IsCarrying(const int a, const int b, 
                const vector<int>& g, const vector<int>& s, 
                const vector<int>& w, const vector<int>& t, 
                long long mid)
{
    long long gold=0;
    long long silver=0;
    long long total=0;

    for (int i = 0; i < s.size(); i++)
    {
            long long now_gold = (long long)g[i];
            long long now_sil = (long long)s[i];
            long long now_w = (long long)w[i];
            long long now_t = (long long)t[i];

            long long move_cnt = mid / (now_t * 2);
            if (mid % (now_t * 2) >= t[i])
                move_cnt++; //편도로 1번더 갈 수 있다면 1회 추가

            gold += (now_gold < move_cnt* now_w) ? now_gold : move_cnt * now_w;
            silver += (now_sil < move_cnt* now_w) ? now_sil : move_cnt * now_w;
            total += (now_gold + now_sil < move_cnt* now_w) ? now_gold + now_sil : move_cnt * now_w;

     }

    if (gold >= a && silver >= b && total >= a + b)
        return true;
    return false;
}

long long solution(int a, int b, vector<int> g, vector<int> s, vector<int> w, vector<int> t)    
{
    long long start = 0;
    long long end = 10e5 * 4 * 10e9;
    long long answer = end;
    while(start <= end)
    {
        long long mid = (start+end)/2;
        
        // 모든 광물을 시간 안에 운반 가능
        if(IsCarrying(a,b,g,s,w,t,mid))
        {
            answer = min(answer, mid);
            end = mid -1;
        }
        // 시간 안에 광물 운반 불가능
        else
        {
            start = mid +1;
        }
    }
    
    return answer;
}