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

해설

금 a kg, 은 b kg를 모으기 위한 최단 시간을 구하는 문제이다.

 "최단 시간"에 포인트를 맞추어 시간 기준으로 문제를 생각해보자.

시간을 기준으로 이분탐색을 진행하고, 탐색하는 시간 내에 금 a, b를 모을 수 있는지 확인하면 된다.

 

using l = long long;

l binarySearch() {
    
    l first = 0;
    l last = 4*1e14+1e5;    
    l ret = last;
    
    while (first <= last) {
        l mid = (first+last)/2;
        if (check(mid)) {
            ret = mid;
            last = mid-1;
        }
        else first = mid+1;
    }
    return ret;
}

 

금 a, b 를 모을 수 있는 시간의 범위에서 first는 0이 된다.

 

1) 그렇다면, last는 어떻게 구해야 할까?

 

문제에서 a, b 의 최대 범위는 10^9 이라고 주어져있다. 이때, 한 번에 옮길 수 있는 무게(w)가 1kg 이고, 편도로 이동할 때 걸리는 시간(t)이 최댓값 10^5 라면 a와 b 만큼 모으는데 가장 긴 시간이 걸릴 것이다.

트럭은 다른 도시에서 먼저 출발하므로, 처음 1kg를 옮길 때 10^5 만큼의 시간이 필요한다.

그 이상의 무게를 옮길 때는 다시 금과 은이 있는 도시로 간 후에 돌아와야 하므로 10^5* 2(왕복)의 시간이 필요하다.

따라서, 이 경우 a와 b만큼을 옮길 때까지 걸리는 시간은 10^5(처음 1kg) + (10^9*2-1)*(10^5*2)(나머지 무게)가 된다.

이를 간략하게 쓰면 10^5 + 10^9*2*10^5*2 = 10^5 + 4*10^14 = 1e5+4*1e14, 즉 4*1e14+1e5 가 시간의 최대 범위가 된다.

 

 

2) 그렇다면, 각 시간 동안 금을 a, 은을 b만큼 모을 수 있는지 어떻게 확인해야 할까?

 

특정 지점에는 금 g[i], 은 s[i] 만큼이 있다.

이동시간은 t[i], 한번 이동할 때 운반 가능한 양은 w[i]이다.

특정 시간 k 동안 트럭이 몇 번 왔다 갔다 할 수 있는지를 구해보면, k / (2*t[i]) 번 만큼 왕복이 가능하다.

이때, 출발지가 특정 지점이므로 왕복을 한 후 남은 시간 k%(2*t[i]) 가 t[i]보다 크거나 같다면, 한번 더 나를 수 있다.

따라서, k%(2*t[i]) >= t[i] 이면 왕복 가능한 횟수에 1을 더해준다.

 

 n = k/(2*t[i]);

if (k%(2*t[i]) >= t[i]) n++;

 

즉, i번째 지점의 경우 k시간 동안 n번 w[i]만큼 광물을 나를 수 있다.

따라서, 금만 운반한다면 운반량은 min(n*w[i], g[i]), 은의 운반량은 min(n*w[i], s[i]), 광물(금+은 합쳐서) 운반향은 min(n*w[i], g[i]+s[i]) 가 된다.

 

모든 지점에서의 금 운반량, 은 운반량, 광물 운반량을 합해 구해놓는다.

k 시간 동안 모든 지점에서의 금 운반량이 a보다 크거나 같고, 모든 지점에서의 은 운반량이 b보다 크거나 같고, 모든 지점에서의 광물 운반량이 (a+b) 보다 크거나 같으면 k 시간 내에 금 a, 은 b 만큼을 운반하는 것이 가능하다.

 

의 두 사실을 이용하여 시간의 최소 범위와 최대 범위 내 이분탐색을 진행하고 시간의 최솟값을 구해 리턴하면 정답이다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using l = long long;

#define X first
#define Y second

bool check(l k, int a, int b, const vector<int>& g, const vector<int>& s, const vector<int>& w, const vector<int>& t) {
    
    l totalg = 0, totals = 0, total = 0;
    for (int i=0; i<(int)g.size(); i++) {
        l rt = t[i]*2;
        l n = k/rt;
        if (k%rt >= t[i]) n++;
        totalg += min(w[i]*n, 1LL*g[i]);
        totals += min(w[i]*n, 1LL*s[i]);
        total += min(w[i]*n, 1LL*g[i]+s[i]);
    }
    
    return totalg >= a && totals >= b && total >= a+b;
}

l binarySearch(int a, int b, const vector<int>& g, const vector<int>& s, const vector<int>& w, const vector<int>& t) {
    
    l first = 0;
    l last = 4*1e14+1e5;    
    l ret = last;
    
    while (first <= last) {
        l mid = (first+last)/2;
        if (check(mid, a, b, g, s, w, t)) {
            ret = mid;
            last = mid-1;
        }
        else first = mid+1;
    }
    return ret;
}


long long solution(int a, int b, vector<int> g, vector<int> s, vector<int> w, vector<int> t) {
    
    return binarySearch(a, b, g, s, w, t);
}