프로그래머스[Lv.3] - 금과 은 운반하기

 

 

문제 설명

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

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

프로그래머스

---

 

 

 

 

 

 

제한 사항

• 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의 모든 수의 합

---

 

 

 

 

 

 

풀이

처음에는 dp를 통해 문제를 풀 수 있다고 생각했다.

하지만 수의 범위가 매우 넓고 조건이 다양하다.

가능은 하겠지만 시간과 메모리가 많이 들 것이다.

 

따라서, 다른 접근법을 이용해야 한다.

바로 parametric search이다.

parametric search는 쉽게 말해 최적화 문제를 결정문제로 변경하는 것이다.

 

즉, 이번 문제에 경우 금과 은을 모두 전달하는 가장 짧은 시간을 찾는 문제이다.

문제를 그대로 해석하면 최적의 시간을 구해내기 위해 연산을 해야 한다.

하지만 생각을 조금 바꿔 임의의 시간  t에 금과 은을 모두 전달할 수 있는지 판단하며 t의 범위를 줄여 나가면 된다는 것이다. 

이때 이진탐색을 이용하면 이 과정을 굉장히 효율적으로 구현하는 것이다.

 

예를 들어, 정답은 3시간이었고 최악의 경우 10시간이 걸린다고 가정해 보자.

우선 0~10 시간 안에 정답이 있기 때문에 중간인 5시간에 금과 은을 모두 옮길 수 있는지 확인한다.정답이 3시간이기 때문에 5시간에는 충분히 옮길 수 있다.그렇기 때문에 우리가 아는 최악의 경우를 5로 변경할 수 있다. 즉, 0~5시간에서 정답을 알아내면 된다.그다음에는 절반인 2시간에 가능한지 확인한다.2시간에는 금과 은을 모두 옮길 수 없다.따라서, 우리가 답을 구해야 하는 범위가 2~5로 갱신된다.이러한 과정을 최악과 최선의 경우의 차이가 1 이하일 때까지 반복하면 된다.

 

이제 금과 은을 옮길 수 있는지를 판단하는 과정만 구현하면 된다.우선 트럭이 모든 도시를 동시에 이동할 수 있다는 것을 인지해야 한다.따라서 순차적인 방법보다 총합을 더해 가능한지 여부를 판단하면 쉽다.

금과 은을 모두 옮기려면 3가지 조건을 만족해야 한다.

• 옮길 수 있는 전체 무게 >= a+b
• 옮길 수 있는 금 무게 >= a
• 옮길 수 있는 은 무게 >= b

임의의 시간 t가 정해진다면 t[i]로 인해 옮길 수 있는 횟수가 정해진다.

횟수가 정해지면 옮길 수 있는 무게도 정해진다.

만약 옮길 수 있는 무게가 도시에 있는 금이나 은보다 많다면 말이 안 되는 상황이기 때문에 둘 중 작은 것을 택한다.

min(cnt * w[i], static_cast<long long>(g[i] + s[i]));

 

금과 은같은 경우도 동일하게 적용한다.

goldSum += min(temp, static_cast<long long>(g[i]));
silverSum += min(temp, static_cast<long long>(s[i]));

 

모든 총합을 구한 뒤 위에서 말한 3가지의 조건이 모두 가능한지 확인하면 된다.

if (total >= a+b && goldSum >= a && silverSum >= b) return true;
return false;

---

 

 

 

 

 

전체 코드

#include <string>
#include <vector>
#include <set>

using namespace std;

bool possible(int a, int b, vector<int>& g, vector<int>& s, vector<int>& w, vector<int>& t, long long time)
{
    int n = g.size();
    long long total = 0;
    long long goldSum = 0;
    long long silverSum = 0;

    for (int i = 0; i < n; i++) {
        long long cnt = time / (2 * t[i]);
        if ((time / t[i]) % 2 == 1) cnt++;

        //옮길 수 있는 무게(금+은)
        long long temp = min(cnt * w[i], static_cast<long long>(g[i] + s[i]));
        
        //전체 무게
        total += temp;
        
        //옮길 수 있는 금, 은
        goldSum += min(temp, static_cast<long long>(g[i]));
        silverSum += min(temp, static_cast<long long>(s[i]));
    }

    if (total >= a+b && goldSum >= a && silverSum >= 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 answer = -1;
    long long high = 1e9 * 2 * 1e5 * 2;
    long long low = 0;
    
    while(low + 1 < high)
    {
       long long mid = (low + high) / 2;

        if (possible(a, b, g, s, w, t, mid)) high = mid;
        else low = mid;
    }
    
    return high;
}

---