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

아이디어

• [이분탐색]을 활용할 줄 안다.
• 이분탐색을 이용한 [파라매트릭 서치]를 활용할 줄 안다

접근방식

1. 이분탐색에서의 start, end를 입력 범위를 보고 정해준다. 이분탐색의 값은 구해야하는 값인 걸리는 시간으로 잡는다
2. 이분탐색을 시행하면서 해당 시간내에 운반할 수 있는 횟수(편도 +1번도 생각)를 구한다
3. 운반횟수안에 각 도시에서 최대로 옮길수 있는 금, 최대로 옮길수 있는 은, 최대로 옮길수 있는 모든 광물(금+은)의 무게들을 저장해준다
4. 목표로하는 금, 은, 금과은을 합친 무게에 각각 해당하는 것들이 만족하면, 시간안에 해결할 수 있다는 의미이므로, end를 감소시킨다
5. 만약 하나라도 만족하지 않는다면, start를 증가시켜, 목표 시간을 늘린다

#include <string>
#include <vector>

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 = 10e5 * 4 * 10e9;

    long long start = 0;
    long long end = 10e5 * 4 * 10e9;

    while (start <= end) {
        long long mid = (start + end) / 2;

        long long gold_carry = 0;
        long long sil_carry = 0;
        long long add_carry = 0;

        for (int i = 0; i < s.size(); i++) {
            long long now_gold = (long long)g[i];
            long long now_sil = (long long)s[i];
            long long now_w = (long long)w[i];
            long long now_t = (long long)t[i];

            long long move_cnt = mid / (now_t * 2);
            if (mid % (now_t * 2) >= t[i]) move_cnt++; //편도로 1번더 갈 수 있다면 1회 추가

            gold_carry += (now_gold < move_cnt* now_w) ? now_gold : move_cnt * now_w;
            sil_carry += (now_sil < move_cnt* now_w) ? now_sil : move_cnt * now_w;
            add_carry += (now_gold + now_sil < move_cnt* now_w) ? now_gold + now_sil : move_cnt * now_w;

        }

        if (gold_carry >= a && sil_carry >= b && add_carry >= a + b) {
            end = mid - 1;
            answer = min(mid, answer);
        }
        else {
            start = mid + 1;
        }

    }

    return answer;
}

평가

월간 코딩 챌린지 시즌3로 나온 문제.
문제 자체가 굉장히 신선하고 재밌는 문제라는 생각이 들었습니다.
이 문제는 최소시간 을 구하고, 무게의 범위가 10^9, 즉 10억정도로 매우 크다는 것에서 이분탐색과 파라매트릭 서치를 사용할 수도 있겠다는걸 눈치채야 하는 문제였습니다.
알고 있는 사람은 어렵지 않게 풀 수 있지만,
파라매트릭 서치가 생소한 사람이라면 몇시간 고민해도 떠오르기 힘든 문제이지 않을까 싶습니다.
또한, 이분탐색에서의 start와 end범위도 잘 지정해줘야합니다.
필자는, end 범위를 무작정 10억으로 잡았다가, 계속 틀려 입력을 잘 고려해보니 10e5 X 4 X 10e9 정도의 범위까지 가능하다는 것을 깨닫고 고쳤었습니다.