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

Kim Yuhyeon·2023년 8월 11일

알고리즘 + 자료구조

목록 보기

123/161

문제

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

알고리즘 접근 방법

이분 탐색 과 파라매트릭 서치 를 활용한다.
1. 구해야 하는 값인 시간을 start , end 로 정한다.
2. 범위를 기반으로 이분 탐색을 진행한다.

mid 시간을 기준으로

최대로 옮길 수 있는 금의 양 : gold

최대로 옮길 수 있는 은의 양 : silver

최대로 옮길 수 있는 자원의 양 : weight 라고 했을 때

weight가 a + b 이상 && gold가 a 이상 && silver가 b 이상일 경우 조건에 부합
-> 시간을 줄여준다 : mid = end - 1

아닐 경우 시간을 늘려준다 : mid = start + 1

풀이

#include <string>
#include <vector>
#include <climits>

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 = LLONG_MAX;
        
    // 이분탐색 start, end 초기화 (걸리는 시간)
    long long start = 0;
    long long end = 10e5 * 2 * 2 * 10e9; // 도시 수 * 재화 수 * 왕복 * 재화량 

    // 이분탐색을 시행하면서
    while (start <= end) {
        long long mid = (start + end) / 2;

        long long gold = 0;
        long long silver = 0;
        long long weight = 0;

        for (int i = 0; i < g.size(); i++) {
            // 각 도시의 왕복 횟수 계산
            long long cnt = (mid + t[i]) / (t[i] * 2);

            // 금을 최소값으로 추가 (트럭의 운반 무게를 고려하여)
            gold += min(g[i] * 1LL, w[i] * cnt * 1LL);

            // 은을 최소값으로 추가 (트럭의 운반 무게를 고려하여)
            silver += min(s[i] * 1LL, w[i] * cnt * 1LL);

            // 금과 은의 합을 최소값으로 추가 (트럭의 운반 무게를 고려하여)
            weight += min((g[i] + s[i]) * 1LL , w[i] * cnt * 1LL);
        }

        // 조건 검사
        if (weight >= a + b && gold >= a && silver >= b) {
            // 현재 시간을 최소값으로 업데이트
            answer = min(answer, mid);
            end = mid - 1;  // 가능한 더 작은 시간을 탐색하기 위해 범위를 줄임
        } else {
            start = mid + 1;  // 시간을 늘려서 더 큰 시간을 탐색
        }
    }

    return answer;
}