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

금과 은 운반하기

문제 링크

금과 은 운반하기

분석

각 도시의 트럭을 최적으로 운영했을 때, 새로운 도시를 건설하기 위한 금과 은을 전달할 수 있는 가장 빠른 시간을 구해 반환해주어야 합니다.

• a와 b는 필요한 금과 은의 양입니다.
• g[i]와 s[i]는 i번 도시에서 가지고 있는 금과 은의 양입니다.
• t[i]는 i번 도시에서 새로운 도시를 건설하는 장소와 걸리는 편도 시간을 의미합니다.
• w[i]는 i번 도시에서 한번에 옮길 수 있는 최대 무게입니다.

즉 다음과 같이 정리 됩니다.

각 도시에서 한번에 금과 은을 합쳐서 w[i]만큼 운반이 가능 합니다.
이때, 한번 왕복에 걸리는 시간은 t[i]입니다.

이분 탐색으로 문제를 풀어낼 수 있습니다.

풀이

#include <vector>
#include <algorithm>

using namespace std;

bool check(int a, int b, const vector<int>& g, const vector<int>& s, const vector<int>& w, const vector<int>& t, long long mid)
{
    long long total = 0;
    long long totalG = 0;
    long long totalS = 0;
    
    for (int i = 0; i < g.size(); ++i)
    {
        long long count = mid / (2LL * t[i]);
        
        if (mid % (2LL * t[i]) >= t[i])
        {
            ++count;
        }
        
        long long carry = min(count * w[i], static_cast<long long>(g[i]) + s[i]);
        total += carry;
        totalG += min(carry, static_cast<long long>(g[i]));
        totalS += min(carry, static_cast<long long>(s[i]));
    }
    
    return total >= a + b && totalG >= a && totalS >= b;
}

long long solution(int a, int b, vector<int> g, vector<int> s, vector<int> w, vector<int> t) {
    long long min = 0;
    long long max = 4e14;
    
    while (min < max)
    {
        long long mid = min + (max - min) / 2;
        if (check(a, b, g, s, w, t, mid))
        {
            max = mid;
        }
        else
        {
            min = mid + 1;
        }
    }
    
    return max;
}

성능 요약

시간 복잡도는 $O(n)$입니다.

• 이분 탐색 횟수 $O(log_2(4e14) \approx 49)$
• check함수 $O(n)$
  • n은 도시의 수를 의미합니다.
• $O(49 \times n)$

공간 복잡도는 고정된 크기의 상수 공간을 사용하기 때문에 $O(1)$입니다.

테스트 성능

테스트 1 〉 통과 (0.01ms, 3.68MB)
테스트 2 〉 통과 (0.01ms, 4.43MB)
테스트 3 〉 통과 (0.01ms, 4.12MB)
테스트 4 〉 통과 (0.01ms, 4.13MB)
테스트 5 〉 통과 (0.01ms, 3.66MB)
테스트 6 〉 통과 (0.02ms, 4.2MB)
테스트 7 〉 통과 (0.03ms, 4.13MB)
테스트 8 〉 통과 (0.06ms, 4.19MB)
테스트 9 〉 통과 (0.11ms, 4.15MB)
테스트 10 〉 통과 (0.17ms, 4.2MB)
테스트 11 〉 통과 (6.84ms, 4.82MB)
테스트 12 〉 통과 (14.01ms, 5.91MB)
테스트 13 〉 통과 (19.92ms, 7.28MB)
테스트 14 〉 통과 (26.50ms, 8.5MB)
테스트 15 〉 통과 (35.47ms, 9.88MB)
테스트 16 〉 통과 (39.36ms, 11.1MB)
테스트 17 〉 통과 (59.12ms, 15.1MB)
테스트 18 〉 통과 (64.00ms, 16.2MB)
테스트 19 〉 통과 (67.31ms, 16.3MB)
테스트 20 〉 통과 (63.97ms, 16.5MB)
테스트 21 〉 통과 (65.68ms, 16.5MB)
테스트 22 〉 통과 (70.64ms, 16.3MB)
테스트 23 〉 통과 (67.33ms, 16.4MB)
테스트 24 〉 통과 (0.01ms, 4.42MB)