프로그래머스 금과 은 운반하기(이진 탐색)

망할 프로그래머스 AI가 0~1단계 문제 몇개 좀 풀었다고 3단계 문제를 추천해 줬다..

내가 문제를 맞출 확률이 56%나 된다길래 자존심 상해서 정말 .... 힘들게 풀었다.

나름 뿌듯?

문제
짧게 요약하면 신도시를 건설하는 데에 금a, 은b가 들어가는데 기존 도시 i에 있는 자원을 몇 시간동안 옮겨야 하는지 return하면 된다.

---

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

bool can_transport(long long mid, int a, int b, int g[], int s[], int w[], int t[], size_t t_len) {
    long long total_gold = 0, total_silver = 0, total_weight = 0;

    for(int i = 0; i < t_len; i++){
        long long max_trips = mid / (2 * t[i]);
        if(mid >= t[i] * (2 * max_trips + 1)) max_trips++;
        long long max_transport = max_trips * w[i];
        
        long long available_gold = (g[i] < max_transport) ? g[i] : max_transport;
        long long available_silver = (s[i] < max_transport) ? s[i] : max_transport;
        long long available_combined = (g[i] + s[i] < max_transport) ? g[i] + s[i] : max_transport;

        total_gold += available_gold;
        total_silver += available_silver;
        total_weight += available_combined;
    }

    return (total_gold >= a) && (total_silver >= b) && (total_weight >= a + b);
}

long long solution(int a, int b, int g[], size_t g_len, int s[], size_t s_len, int w[], size_t w_len, int t[], size_t t_len) {
    long long low = 0;
    long long high = 1e15;
    long long answer = high;

    while(low <= high){
        long long mid = (low + high) / 2;
        if(can_transport(mid, a, b, g, s, w, t, t_len)){
            answer = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    return answer;
}

---

 

문제를 푸는 데에 사용된 알고리즘: 이진 탐색

 

트럭 한 대가 w[i]kg만큼의 광물을 옮길 수 있고 편도로 이동하는 데 t[i]시간이 걸린다. 이러한 정보들을 이용해 "최적의 최소 시간"을 구해야 하기 때문에, 최소 시간 low = 0와 최대 시간 high = 1e15(최대한 큰 수)를 임의로 설정해 반복문을 통해 low는 늘리고 high는 줄이면서 결과값 mid를 찾아야 한다.

 

때문에, bool 함수를 만들어서 반복문 내에서 호출한다. bool함수는 mid 시간 내에 i도시의 트럭들이 필요 자원을 모두 옮길 수 있는지 출력해준다.

 

max_trips: 트럭이 왕복 가능한 최대 횟수를 뜻한다. t[i] x 2 를 하면 편도 이동 시간의 두배가 되고, mid에서 그 값을 나누면 횟수가 나온다.

max_transport: 최대로 운반 가능한 최대수송량이다. 왕복 가능한 최대 횟수에서 최대적재량 w[i]를 곱해주었다.

available_gold,silver,combined: 말 그대로. 최대수송량보다 기존 도시의 자원이 적다면 그 자원만큼, 그게 아니라면 최대수송량을 리턴한다.

 

처음엔 여기까지만 작성하고 뿌듯해 했는데.. 왕복운반을 마친 후 남은 시간 내에 할 수 있는 1회의 편도운반이 있었다..

if(mid >= t[i] * (2 * max_trips + 1)): 2t[i] * max_trips + t[i]로, 왕복 시간 * 왕복 횟수 + 편도 시간이다. mid가 이것보다 작거나 같다면 max_trip을 1늘려줘서 최대수송량도 w[i] * 1만큼 늘어나게 된다.

 

---

코딩 고수 친구에게 코드 피드백 받으며 배운 팁

#include<algorithm>

using namespace std; 를 추가하면,

삼항연산자를 안 쓰고도 문제를 풀 수 있는 방법이 있었다!

흰색 = 나

검정색 = 친구

ㅋㅋ

 

여담이지만 원래 코드는 편도 운반 식이 아래에 하나 더 있는 형태였다. 코드를 줄일 수 있는 게 신기했다.

원래의 끔찍한 코드 ^_^

---

 

솔직히 푸느라 너무 힘들었다. 이진 탐색 알고리즘 자체는 쉬웠지만, 함수를 새로 만들어서 호출하는 형태의 문제는 처음 풀어봐서 신선했다. 조건도 이전에 하던 것들보다 꽤 많고 까다로워서 생각할 게 많았던 것 같다.

사실 이 문제는, 내가 질문하기 버튼에 있던 이진 탐색 어쩌구 글을 봐버려서(스포당했다) 구글에서 찾아서 풀 수 있었던 것 같다. 
하지만 이런 문제를 한번 풀어봤으니 앞으론 더 잘 풀 자신이 생겼다.

그리고, 기초를 탄탄히 해야겠다. 알고리즘&자료구조 책을 사서 한번 읽어봐야겠다. 문제를 풀 때 필요한 선수지식이 나에겐 부족한 느낌이다.
이제 sqld시험 준비를 해야한다. 알고리즘 문제는 하루에 하나만 풀어야지. 내 레벨에 맞는 걸로..