[ 프로그래머스 ] 금과 은 운반하기 (C++) - 이분탐색

---

🔗 문제 링크

프로그래머스

---

💡 문제 풀이 및 해석

1. 최악의 경우 모든 금(10^9)+은(10^9) 을 10^5*2 만큼 움직여야 하므로 400조의 시간이 걸린다. 이는 일반적인 방법으로는 해결할 수 없고, "이분탐색"과 같은 방식으로 해결할 수 있을 것으로 보인다.
2. 하지만, 어떤 조건이 성립해야 모두 시간안에 옮길 수 있을까? 라는 조건은 쉽게 생각나지 않는다. (저도 이 부분은 구글링을 했습니다.)
3. 최대로 옮길 수 있는 금의 양 >= a && 최대로 옮길 수 있는 은의 양 >= b && 금+은 통합해서 최대로 옮길 수 있는 무게 >= a+b 가 성립하면, 가능하다. (어찌보면 당연한 조건이다.)
4. 이제 이분탐색에서 left = 0, right = MAX 로 둔 상태로 진행한다면, 쉽게 풀 수 있는 문제가 됩니다.
5. 단, 여기서 예제에서도 알 수 있듯이 트럭이 움직일 수 있는 횟수는 항상 왕복이 아닌 마지막을 "편도"로 끝낼 수 있기 때문에, 최대로 이동할 수 있는 횟수에서 if (mid % (2 * t[i]) >= t[i]) cnt++; // 편도로 한번 더 갈 수 있다면 횟수 + 1 가 들어가는 것.

---

⭐️ 정답 코드 및 설명

#include<iostream>
#include <string>
#include<cmath>
#include <vector>

using namespace std;

// a : 금 , b : 은, g : i번도시금, s : i번도시은, w : 트럭운반최대, t : 이동 시간
long long solution(int a, int b, vector<int> g, vector<int> s, vector<int> w, vector<int> t) {
    long long answer = -1;
    long left = 0, right = 400000000000000;

    while (left < right) {
        long mid = (left + right) / 2;

        long gold = 0, sliver = 0, total = 0;

        for (int i = 0; i < g.size(); i++) {
            long cnt = mid / (2 * t[i]); // i번 마을이 자원을 옮길 수 있는 횟수
            if (mid % (2 * t[i]) >= t[i]) cnt++; // 편도로 한번 더 갈 수 있다면 횟수 + 1

            long weight = min(long(g[i]) + long(s[i]), cnt * w[i]); // 모두 다 옮길 수 있거나 그렇지 않거나

            total += weight; // 최대로 옮길 수 있는 무게
            gold += min(weight, long(g[i])); // 최대로 옮길 수 있는 금
            sliver += min(weight, long(s[i])); // 최대로 옮길 수 있는 은
        }

        // 가능하면
        if (total >= a + b && gold >= a && sliver >= b) right = mid;
        else left = mid + 1;
    }
    return right;
}

---

🤔 문제 후기

그렇게 쉬운문제라고는 생각되지 않는다. 이분 탐색으로 풀어야 될 것 같다고는 생각했지만, 어떤 조건을 만족해야 풀릴지는 생각을 하지 못한 문제다. 아마 이 조건을 찾기가 너무 어려워서 정답률이 낮은게 아닌가 라는 생각이 들었다. (실제로 조건만 찾으면 그렇게 어렵진 않다.) 수학적인 지식이 있다면, 어렵지 않게 풀 수 있는 문제인 것 같다.