[Algorithm] Programmers :: 금과 은 운반하기

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

프로그래머스

bool check(long long time, int a, int b, vector<int>& g, vector<int>& s, vector<int>& w, vector<int>& t)
{
    long long total = 0;
    long long totalG = 0;
    long long totalS = 0;
 
    for (int i = 0; i < g.size(); ++i)
    {
        if (time < t[i]) continue; // 한번의 편도도 이동못하면 안되니까.
 
        long long onewayCount = time / t[i]; // 편도이동 가능한 횟수.
        long long count = 0; // 도시에 광물 건네주는 횟수.
 
        if (onewayCount % 2 == 0) count = onewayCount / 2;
        else count = onewayCount / 2 + 1;
 
        long long tmp = min(count * (long long)w[i], (long long)g[i] + s[i]);
 
        total += tmp;
        totalG += min(tmp, (long long)g[i]);
        totalS += min(tmp, (long long)s[i]);
    }
 
    if (total >= a + b && totalG >= a && totalS >= 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 = 10e14 * 3;
 
    long long left = 0;
    long long right = 10e14 * 3;
 
    while (left <= right)
    {
        long long mid = (left + right) / 2;
 
        if (check(mid, a, b, g, s, w, t))
        {
            right = mid - 1;
            answer = mid;
        }
        else
        {
            left = mid + 1;
        }
    }
 
    return answer;
}

 

주어진 변수들이 많고 최대숫자값도 크기때문에 '시간'을 기준으로 되냐 안되냐만 따지면서 되는시간과 안되는시간의 경계선을 찾는 문제이다. (파라매트릭 서치)

 

다만 주어진 시간이 가능한 시간인건지에 대한 판단(check함수)을 어떻게 해야할지 몰라서 다른분의 풀이를 참고했다.

일단 특정 트럭의 편도이동시간이 주어진 시간보다 높다면 아예 이동을 못하니까 바로 다음 트럭으로 넘어갔다. 

그리고 몫 나누기를 통해 한번의 편도이동시간을 구하고 해당 시간을 2로 나눠(왕복해야하니까) 신도시까지 광물을 전달할 수 있는 최종 수를 구한다.

다만, 왕복이 아니라 딱한번의 편도라도 이동이 가능하다면 갖다 줄 수 있기 때문에 홀수라면, 즉 1이 남는다면(편도이동한번이 남는다면) 한번더 카운팅을 해준다.

 

이후가 중요한데, tmp라는 값은 실제 해당트럭이 신도시에 가져다 줄 수 있는 광물량을 의미한다.

w[i]값은 트럭이 최대 가져다 줄 수 있는 광물량이라서 그저 위에서 구한 onewayCount * w[i]를 해주면 될 것 같지만, 실제로는 해당도시가 보유한 실제광물량은 더 적을 수 있기 때문에 min(count * w[i], g[i] + s[i])를 해준 것이다.

한번에 10000kg를 가져다 줄 수 있더라도 실제 광물량은 100kg밖에 없다면 100kg만 가져다 줄 수 있는 것이다.

 

그렇게 구한 tmp값을 total에다가 누적합을 해준다. 코드를 보면 이전에 함수의 라이프사이클내에 total, totalG, totalS를 선언해놓은 것을 볼 수 있는데 total값은 주어진 시간동안 모든 도시에서 신도시에 가져다 줄 수 있는 '광물량'을 의미하고

totalG는 신도시에 가져다 줄 수 있는 '금', totalS는 은을 의미한다.

앞서 말했듯이 tmp값은 주어진 시간동안 해당 도시에서 신도시에 가져다 줄 수 있는 광물량을 의미하기 때문에 total값에 합산을 해준다. 이 total값들은 최종적으로 가능한지에 대한 판단을 하기위한 값으로 쓰인다.

 

totalG값은 실제로 해당시간동안 해당도시에서 신도시까지 가져다줄 수 있는 금을 의미한다고 했는데, 마찬가지로 적재량에 비해서 가지고 있는 금은 적을 수 있기 때문에 min(tmp, g[i])값을 적용한다.

 

최종적으로 판단할때 조건이 세가지가 있다. 

1. total >= a + b

2. totalG >= a

3. totalS >= b

 

1번같은 경우는 전체광물량을 비교하는 것인데, 당연히 요구량보다 같거나 높아야 적절하다고 볼 수 있다.

2,3번도 비슷한 느낌으로 운반가능한 모든도시에서 가능한 최대의 금을 옮겼는데도 불구하고 요구량 a값보다 낮으면 조건에 맞지 않는다. 은도 마찬가지..