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

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/86053

프로그래머스

새로운 도시를 짓기위해 여러 나라에서 금과 은을 운송한다. 이때 필요한 금과 은을 모두 운송하기위해 필요한 최소 시간을 구해보자.

 

풀이

 각 도시마다 자원의 양이 한정되어있고, 한 번에 운반할 수 있는 양과, 한 번 운반에 필요한 시간이 모두 다르다.

최적의 시간을 구하기 위해서 모든 경우의 수를 다 따져보기엔 말이 안된다.

그래서 나는 제한시간을 걸어두고, 이 시간안에 정해진 금과 은을 옮길 수 있는지 여부를 파악하려했다.

이때 제한시간은 이분탐색을 통해 설정해준다.

그렇다면 초기 범위인 L과 R값을 정해줘야하는데, L은 최소시간이므로 간편하게 0으로 설정하자.

R은 최악의 경우에 걸리는 시간으로 설정해줘야하는데

자원을 운반할 도시가 하나만 있고, 운반할 수 있는 양은 1회에 1만 이동가능하고, 편도에 필요한 시간은 10^5 라고 최악의 조건을 걸어보자.

금과 은은 각각 10^9만큼 필요하다. 따라서 총 운반해야할 양은 2 * 10^9.

마지막 운반때는 왕복이 아닌 편도로만 이동하면 되므로

마지막 운반 : 10^5시간 사용, 1 운반

나머지 운반 : 2 * 10^5시간 사용, 1운반

따라서 총 걸리는 시간은 10^5 + (2 * 10^9 - 1) * 2 * 10^5 이다.

이때 2 * 10^9 에서 1빼는건 거의 의미가 없는 계산이므로 2 * 10^9로 생각하면

4 * 10^14 + 10^5가 최악의 경우 걸리는 시간이다. 이 값을 R로 설정해준다.

 

이분 탐색을 이용해서 mid시간 안에 정해진 양을 운반이 가능하면 R = mid -1로 시간이 작아질 수 있도록 유도한다.

반대로 mid시간 안에 정해진 양을 운반하지 못하면 L = mid + 1로 시간이 커질 수 있도록 유도한다.

 

1. 모든 도시에서 운반 가능한 총 금의 양을 구한다. (이하 Gold)

2. 모든 도시에서 운반 가능한 총 은의 양을 구한다. (이하 Silver)

 

Gold 값이 운반해야할 금의 양 a 보다 크고, Silver 값이 운반해야할 은의 양 b보다 크면

즉, (Gold >= a && Silver >= b)면 시간 내에 운반이 가능하다고 판단하면 될까??

답은 아니다.

만약 두 도시가 있고, 금과 은을 각각 10만큼 운반해야한다고 가정하자.

1번 도시는 금과 은을 10씩 가지고 있으며, 편도 5시간, 1회 운반에 5만큼 운반 가능.

2번 도시는 금과 은을 10씩 가지고 있으며, 편도 10시간, 1회 운반에 1만큼 운반 가능.

만약 주어진 시간 mid가 15시간이라고 한다면

1번 도시는 10 + 5 => 2회 운반 가능하므로 운반 가능한 금과 은은 각각 10

2번 도시는 10 + 0 => 1회 운반 가능하므로 운반 가능한 금과 은은 각각 1

Gold, Silver 값은 11이고 이는 모두 10보다 크니까

(Gold >= a && Silver >= b) 조건을 만족한다. 하지만 1번 도시가 금을 10옮기는 동안 2번 도시는 은을 1만큼 밖에 옮기지 못하므로 a만 충족되고 b는 충족되지 않는다.

 

따라서 조건이 하나 추가되어야한다.

금, 은 상관없이 모든 도시에 시간 내에 운반 가능한 자원의 총 합을 Total 이라고 하자.

Total >= a + b 를 만족해야 금과 은을 모두 충족시킬 수 있다.

따라서 (Total >= a + b && Gold >= a && Silver >= b) 조건을 만족해야 운반 가능한 것이라 판단을 내린다.

 

코드 작성

#include <bits/stdc++.h>
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 = -1;
    long long L = 0; long long R = 4 * pow(10,14) + pow(10,5);// 최악의 경우
    
    if(a == 0 && b == 0)
        return 0;
    
    while(L <= R){
        long long mid = (L + R) / 2; //mid시간 안에 물자 조달이 가능한가?
        long long Gold = 0;
        long long Silver = 0;
        long long Total = 0;
        for(int i = 0; i<w.size(); i++){
            long long move = (mid + t[i]) / (t[i] * 2); //운반 횟수
            Gold += min((long long)g[i], move * w[i]);
            Silver += min((long long)s[i], move * w[i]);
            Total += min((long long)g[i] + s[i], move * w[i]); 
        }
        if(Total >= a + b && Gold >= a && Silver >= b){
            R = mid - 1;
            if(answer == -1)
                answer = mid;
            else answer = min(answer, mid);
            continue;
        }
        else{
            L = mid + 1;
        }
    }
    return answer;
}