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

문제 설명

어느 왕국에 하나 이상의 도시들이 있습니다. 왕국의 왕은 새 도시를 짓기로 결정하였습니다. 해당 도시를 짓기 위해서는 도시를 짓는 장소에 금 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 함수를 완성해주세요.

제한사항

• 0 ≤ a, b ≤ 109
• 1 ≤ g의 길이 = s의 길이 = w의 길이 = t의 길이 = 도시 개수 ≤ 105
• 0 ≤ g[i], s[i] ≤ 109
• 1 ≤ w[i] ≤ 102
• 1 ≤ t[i] ≤ 105
• a ≤ g의 모든 수의 합
• b ≤ s의 모든 수의 합

---

풀이

실패
우선 주어진 조건을 통해 최대 범위를 생각했을 때, 이건 이진탐색을 이용한 문제라는 것을 빠르게 유추해낼 수 있었다. 그래서 주어진 조건을 만족하는 최소 시간을 찾는 Parametric search 를 떠올려 바로 적용했다.
그런데 조건을 만족하는지 판별하는 식이 쉽게 떠오르지 않았다. 시간 내 옮길 수 있는 최대 금의 양이 a보다 크고 옮길 수 있는 최대의 은의 양이 b보다 크더라도, 각 트럭이 옮기는 비율에 따라 두 조건을 동시에 만족하지 못하는 경우도 있다고 생각했기 때문이다. 결국 풀이를 찾아보게 되었는데, 두 조건을 동시에 만족하려면 ‘옮길 수 있는 최대 광물의 양이 a+b보다 커야한다’라는 조건이 추가되어야 한다는 것을 확인할 수 있었다.
‘만약 옮길수 있는 최대 광물의 양이 a + b 보다 커야한다’는 조건을 먼저 떠올렸다면, 그리고 나서 ‘최대 금/은의 양이 a/b 보다 커야 비율을 나눌 수 있다’의 조건을 떠올릴 수 있었을 것 같은데, 아쉬운 부분이다.

코드

// 09:55 ~ 
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

long long solution(int a, int b, vector<int> g, vector<int> s, vector<int> w, vector<int> t) {
    long long low = 0, high= 10e9 * 2 * 10e5 * 2, mid;
    long long total_g,total_s,total_w;
    long long goback_cnt;
    int n = g.size();
    while(low < high){
        mid = low + (high-low)/2;
        total_g = 0; total_s =0; total_w = 0;
        for(int i =0; i < n; ++i){
            if(t[i] > mid) continue;
            goback_cnt = (mid - t[i]) / ( 2 * t[i]);
            total_g += min((long long)g[i], (goback_cnt + 1) * w[i]);
            total_s += min((long long)s[i], (goback_cnt + 1) * w[i]);
            total_w += min((long long)(g[i] + s[i]), (goback_cnt + 1) * w[i]);
        }
        if(total_g >= a && total_s >= b && total_w >= a+b){
            high = mid;
        }
        else low = mid + 1;
    }
    return high;
}