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

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

프로그래머스

 

왕국에 새로운 도시를 짓기 위해 금 a kg과 은 b kg을 특정 장소로 옮겨야 합니다. 각 도시는 트럭을 보유하고 있으며, 트럭은 금과 은을 동시에 운반할 수 있습니다. 각 트럭은 다음과 같은 특징을 가집니다:

• i번 도시의 트럭:
  • 금 g[i] kg, 은 s[i] kg 보유.
  • 편도 이동 시간 t[i].
  • 최대 적재량 w[i].

모든 트럭은 특정 도시와 건설 장소를 왕복하며, 최적의 운행으로 금과 은을 건설 장소로 옮기는 데 걸리는 최단 시간을 계산하는 문제입니다. 주어진 정보(a, b, g, s, w, t)를 기반으로 가장 빠른 시간을 구해야 합니다.

 

풀이 방법

이번 문제는 금과 은을 새로운 도시로 옮기는 데 걸리는 최소 시간을 구하는 최적화 문제입니다.
이를 해결하기 위해 파라메트릭 서치와 이진 탐색을 활용했습니다.

 

파라메트릭 서치란?

파라메트릭 서치는 최적화 문제를 결정 문제로 바꿔 해결하는 방식입니다.
즉, 문제의 상황을 만족하는 특정 변수(예: 시간)의 최솟값이나 최댓값을 구하기 위해,
다음 두 가지 조건을 만족해야 합니다:

1. 정답 여부를 쉽게 판단 가능해야 함:
   주어진 시간 안에 금과 은을 목표량 이상 운반할 수 있는지 판단할 수 있어야 합니다.
2. 정답 범위가 연속적이어야 함:
   특정 시간이 조건을 만족한다면, 그보다 긴 시간도 조건을 만족하며, 반대로 특정 시간이 조건을 만족하지 않으면 그보다 짧은 시간도 조건을 만족하지 않습니다.

---

그리고 이진 탐색을 통해 최소 시간을 효율적으로 탐색합니다.
t[i] 값이 크거나 트럭의 수가 많아질수록 모든 경우를 계산하면 시간이 크게 증가하기 때문에,
이진 탐색으로 탐색 범위를 줄여가며 최적의 시간을 찾으면 됩니다.

 

 

풀이 코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

long long solution(int a, int b, vector<int> g, vector<int> s, vector<int> w, vector<int> t) {
    
    long long max_time = 0;
    for (int i = 0; i < g.size(); i++) {
        long long total_weight = (long long)(a + b);
        long long trips = (total_weight + w[i] - 1) / w[i];
        long long city_time = (trips - 1) * 2 * t[i] + t[i];
        max_time = max(max_time, city_time);
    }
    
    long long answer = -1;
    //시간 기준 
    long long left = 0; 
    long long right = max_time;
    
    //이진탐색
    while(left <= right){
        long long mid = (left+right)/2;
        
        long long total_g = 0;
        long long total_s = 0;
        long long total_gs = 0;
        
        for(int i=0; i<g.size(); i++){
            long long trips = mid / (2*t[i]);
            if (mid % (2 * t[i]) >= t[i]) trips++;
            
            // cout << "trips: " << trips <<'\n';
            
            long long max_transport = trips*w[i];
            total_g += min((long long)g[i], max_transport);
            total_s += min((long long)s[i], max_transport);
            total_gs += min((long long)g[i]+s[i], max_transport);
            
             // cout << "total_g: " << total_g <<'\n';
             // cout << "total_s: " << total_s <<'\n';
             // cout << "total_gs: " << total_gs <<'\n';
        }
        
        if(total_g >= a && total_s >= b && total_gs >= (a+b)){
            answer = mid;
            right = mid - 1;
        } 
        else {
            left = mid + 1;
        }
    }
    return answer;
}