20240329_금과 은 운반하기(프로그래머스)

오늘의 TIL은 금과 은 운반하기라는 프로그래머스의 문제에 대한 내용이다.

 

문제 링크

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

프로그래머스

 

 

문제 설명

어느 왕국에 하나 이상의 도시들이 있다.

도시를 짓기 위해서는 도시를 짓는 장소에

금 a(kg)과 은 b(kg)이 전달되어야 한다.

 

각 도시에는 번호가 매겨져 있는데,

i번 도시에는 금 g[i](kg), 은 s[i](kg), 그리고 트럭 한 대가 있다.

i번 도시의 트럭은 오직 새 도시를 짓는 건설 장소와 i번 도시만을 왕복할 수 있으며

편도로 이동하는데 t[i] 시간이 걸리고, 최대 w[i](kg)의 광물을 운반할 수 있다.

모든 트럭은 같은 도로를 여러 번 왕복할 수 있으며, 연료는 무한대라고 가정한다.

 

정수 a, b와 정수 배열 g, s, w, t가 매개변수로 주어질 때,

주어진 정보를 바탕으로 각 도시의 트럭을 최적으로 운행했을 때,

새로운 도시를 건설하기 위해 금 a(kg)과 은 b(kg)을

전달할 수 있는 가장 빠른 시간을 구해 return 하시오.

 

 

제한 조건

0 <= a, b <= 10^9
1 <= g의 길이 = s의 길이 = w의 길이 = t의 길이 = 도시의 개수 <= 10^5
0 <= g[i], s[i] <= 10^9
1 <= w[i] <= 10^2
1 <= t[i] <= 10^5
a <= g의 모든 수의 합
b <= s의 모든 수의 합

 

 

해결 방안

문제에서 헷갈릴 수 있는 것이

지금 새로운 도시를 건설하는데 이 도시와 연결된 도시들을 배열로 주어주는 것이다.

즉, a, b를 만족하기 위해 최단 시간을 사용하는 방법을 찾는 문제인데

금과 은의 두 개의 변수를 가지고 있으며, 이를 동시에 운반하는 것도 가능한 점을 고려해야한다.

또 a와 b를 옮기는 과정에서 시간을 많이 사용하게 되는 방법이 있다면

그 시간동안 나머지를 다 옮기더라도 답은 가장 오래 걸리는 시간이 된다.

 

 

통과한 답안

using System;

public class Solution {
    public long solution(int a, int b, int[] g, int[] s, int[] w, int[] t) {
        
        long left = 0;
        long right = (long)1e15;
        long answer = right;

        while (left <= right)
        {
            long mid = (left + right) / 2;
            if (Check(mid, a, b, g, s, w, t))
            {
                answer = mid;
                right = mid - 1;
            }
            else
            {
                left = mid + 1;
            }
        }
        return answer;
    }
    private static bool Check(long time, int a, int b, int[] g, int[] s, int[] w, int[] t)
    {
        long totalGold = 0;
        long totalSilver = 0;
        long total = 0;

        for (int i = 0; i < g.Length; i++)
        {
            long trips = time / (t[i] * 2);
            if (time % (t[i] * 2) >= t[i]) trips++;
            long capacity = trips * w[i];

            long gold = Math.Min(capacity, g[i]);
            totalGold += gold;

            long silver = Math.Min(capacity, s[i]);
            totalSilver += silver;

            total += Math.Min(capacity, g[i] + s[i]);
        }

        return totalGold >= a && totalSilver >= b && total >= a + b;
    }
}

 

 

주어진 시간이 필요한 금과 은을 운반할 수 있는지 확인하는 Check 함수 구현

private static bool Check(long time, int a, int b, int[] g, int[] s, int[] w, int[] t)
{
    long totalGold = 0;
    long totalSilver = 0;
    long total = 0;

    for (int i = 0; i < g.Length; i++)
    {
        long trips = time / (t[i] * 2);
        if (time % (t[i] * 2) >= t[i]) trips++;
        long capacity = trips * w[i];

        long gold = Math.Min(capacity, g[i]);
        totalGold += gold;

        long silver = Math.Min(capacity, s[i]);
        totalSilver += silver;

        total += Math.Min(capacity, g[i] + s[i]);
    }

    return totalGold >= a && totalSilver >= b && total >= a + b;
}

 

Check 함수를 만들어서 지금 사용하는 시간이 

필요한 금과 은을 운반할 수 있는지 확인하는 함수를 구현한다.

각 도시별로 주어진 시간(time) 안에 트럭이 왕복할 수 있는 횟수(trips)를 계산하고,

만약 편도 추가가 가능하다면, 횟수를 1 증가시킨다.

각 도시의 트럭이 운반할 수 있는 최대 광물의 양(capacity)을 계산한다.

이 capacity를 사용해서 각 도시에서 운반할 수 있는 금과 은을 계산하고

운반 가능한 최대 양과 각 도시가 갖고 있는 양 중에서 작은 값을 택한다.

마지막으로 총 운반된 금과 은, 둘의 합을 계산하고

금이 a보다 크고, 은이 b보다 크고, 총량이 a + b 이상이라면 true를 반환한다.

 

이를 통해서 지금 주어진 시간(time)이 조건을 만족하는지 확인할 수 있다.

 

 

이진 탐색을 이용해서 조건을 충족하는 최소 시간 구하기

long left = 0;
long right = (long)1e15;
long answer = right;

while (left <= right)
{
    long mid = (left + right) / 2;
    if (Check(mid, a, b, g, s, w, t))
    {
        answer = mid;
        right = mid - 1;
    }
    else
    {
        left = mid + 1;
    }
}
return answer;

 

left(0)와 right(long에서의 최댓값)를 설정한다.

while 문을 이용하여 left와 right의 중간값(mid)을 설정하고

Check함수를 이용하여 mid의 시간이 조건을 충족하는지 확인한다.

 

만약 충족한다면 right를 mid - 1로 설정하여 탐색의 범위를 줄이고,

충족하지 않는다면 left를 mid + 1로 설정하여 탐색의 범위를 줄인다.

left가 right보다 큰 경우까지 반복하여 가장 적게 걸리는 시간을 answer로 저장한다.

 

 

오늘은 프로그래머스의 추천 문제로 나온 금과 은 운반하기라는 문제를 풀이해보았는데

처음에는 이진 탐색을 사용하지 않고 풀이하려고 하니 시간 초과가 나는 경우가 발생했다.

따라서 이진 탐색을 사용하게 되었는데, 이진 탐색은 매우 큰 범위의 문제라도

logN의 수준으로 빠르게 탐색할 수 있으므로 이를 사용하는 것이 타당하다고 깨달았다.

 

이진 탐색을 사용하는데 있어서 이를 판단할 Check 함수도 작성하였는데

모든 경우의 수들을 가지고 이 경우에 필요한 조건을 만족하는 함수를 작성하는 과정에서

금과 은의 양이 각 도시가 갖고 있는 양으로 충분한지 확인하기 위해

도시에 있는 금과 은의 양의 합과 필요한 금과 은의 양의 합을 비교하는 과정을 추가함으로써

판단하며 생겼던 문제를 해결할 수 있었다.

 

오늘은 알고리즘 문제를 풀면서 이진 탐색에 대해 조금 더 공부할 수 있는 시간을 가졌다고 생각한다.