금과 은 운반하기

문제

https://programmers.co.kr/learn/courses/30/lessons/86053?language=cpp

코드

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

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 = 400000000000000;
    long long high = answer;
    long long low = 0;
    while(low <= high){
        long long mid = (low+high)/2;
        long long t_sum = 0;
        long long g_sum = 0;
        long long s_sum = 0;
        for(int i=0; i<t.size(); i++){
            long long cur_g = (long long)g[i];
            long long cur_s = (long long)s[i];
            long long cur_w = (long long)w[i];
            long long cur_time = (long long)t[i];

            long long cnt = ((mid/cur_time+1)/2);
            long long tot = cur_w*cnt;
            t_sum += (tot <= cur_g + cur_s ? tot : cur_g + cur_s);
            g_sum += (tot <= cur_g ? tot : cur_g);
            s_sum += (tot <= cur_s ? tot : cur_s);
        }

        if(t_sum >= a+b && g_sum >= a && s_sum >= b){
            answer = (answer >= mid ? mid : answer);
            high = mid-1;
        }else{
            low = mid+1;
        }


    }



    return answer;
}

피드백

• 이 문제는 코드챌린지에 나왔던 문제이다.
• 당시에 이분탐색인건 접근했는데, 금과 은을 어떻게 할지를 몰라서 못 푼 문제이다.
• 금, 은, 금+은에 대해서 가능한 값을 찾고 합산해주면 되는 문제이다.
• 각 항목의 경우 가능한 값을 찾는 것은 다음과 같다.
  • `Min(운반 가능한 양, 전체 양)
• 각 도시에서 각 항목에 대한 가능한 값을 찾아 집계해서 다음의 식을 만족하면 답의 후보로 찾는 방식이다.
  • tot >= a+b && gSum >= a && sSum >= b
  • 이렇게 해도 되는 이유는 다음과 같다.
  • 먼저 금 요구량과 은 요구량을 합산한 양을 옮길 수 있는 지 찾는 것은 자명하다.
  • 위 조건을 만족하고 금 운반량이 금 요구량보다 크고, 은 운반량이 은 요구량 보다 크면 그 안에서 알아서 금, 은 요구량을 맞출 수 있기 때문에 위 조건을 만족하면 그것이 해이다.
  • 이 해 중 가장 최적인 해를 빠르게 찾기 위해 이분 탐색을 쓰는 것이다.
• 문제는 바보값이, 전체 양도 Min(운반 가능한 양, 전체 양) 하는 것을 해주지 않아서 시간을 많이 날렸다. ㅜㅜ