[프로그래머스] 월간 코드 챌린지 시즌3 - 금과 은 운반하기 (Java)

 

코딩테스트 연습 - 금과 은 운반하기

문제 설명

어느 왕국에 하나 이상의 도시들이 있습니다. 왕국의 왕은 새 도시를 짓기로 결정하였습니다. 해당 도시를 짓기 위해서는 도시를 짓는 장소에 금 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 하도록 solution 함수를 완성해주세요.

---

제한사항

• 0 ≤ a, b ≤ 109
• 1 ≤ g의 길이 = s의 길이 = w의 길이 = t의 길이 = 도시 개수 ≤ 105
  • 0 ≤ g[i], s[i] ≤ 109
  • 1 ≤ w[i] ≤ 102
  • 1 ≤ t[i] ≤ 105
  • a ≤ g의 모든 수의 합
  • b ≤ s의 모든 수의 합

---

입출력 예

a	b	g	s	w	t	result
10	10	[100]	[100]	[7]	[10]	50
90	500	[70,70,0]	[0,0,500]	[100,100,2]	[4,8,1]	499

---

입출력 예 설명

입출력 예 #1

• 도시가 오직 하나뿐이므로, 0번 도시의 유일한 트럭이 모든 운반을 해결해야 합니다. 이 트럭은 최대 7kg만큼의 광물을 운반할 수 있으며 편도 완주에는 10시간이 걸립니다.
• 맨 처음에 10시간을 써서 7kg만큼의 금을 운반하고, 10시간을 써서 다시 도시로 돌아오고, 10시간을 써서 7kg만큼의 은을 운반하고, 10시간을 써서 다시 도시로 돌아오고, 마지막으로 10시간을 써서 3kg만큼의 금과 3kg만큼의 은을 운반하면, 총 50시간 만에 필요한 모든 금과 은을 조달할 수 있습니다.
• 따라서, 50을 return 해야 합니다.

입출력 예 #2

• 도시가 3개이고, 0번과 1번 도시는 금만 70kg씩 가지고 있고 2번 도시는 은을 500kg 가지고 있습니다.
  • 0번 도시의 트럭은 용량은 100kg, 편도 완주 시간은 4시간입니다.
  • 1번 도시의 트럭은 용량은 100kg, 편도 완주 시간은 8시간입니다.
  • 2번 도시의 트럭은 용량은 2kg, 편도 완주 시간은 1시간입니다.
• 금은 0번 도시의 트럭과 1번 도시의 트럭이 각각 45kg씩 나누어서 운반하면 8시간 안에 필요한 모든 금을 조달할 수 있습니다.
• 은은 2번 도시의 트럭이 한 번에 2kg씩 250번 운반하면(249번 왕복 + 1번 편도) 총 499시간 만에 필요한 모든 은을 조달할 수 있습니다.
• 따라서, 499를 return 해야 합니다.

---

풀이

나에겐 너무 어려웠던 문제.. (벽 느낌)

이분탐색을 물어보는 문제였지만, 수학적인 성립 조건을 도출하기까지 쉽지 않았다.

 

아래 글들을 참고하여 겨우겨우 문제를 이해할 수 있었다.

[월간 코드 챌린지 시즌3] 9월 문제 해설

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

[ 프로그래머스 [ 월간코드챌린지 ] 금과 은 운반하기 ] (C++)

 

우선 이분탐색을 적용해야한다는 것을 알아내기 위해서는 관점의 전환이 필요했다. 금과 은을 얼마나 빠른 시간 안에 운반할 수 있을까?가 아닌 T라는 시간이 주어졌을 때 이 시간 안에 목표하는 금과 은(a, b)를 운반이 가능한가?라는 관점으로 접근해야한다. (이렇게 예-아니오로 결론이 나는 문제를 결정 문제라고 한단다.)

 

그렇다면 이분탐색을 수행할 때 중간값의 아래쪽을 이어서 탐색할지, 위쪽을 이어서 탐색할지에 대한 결정 기준은 어떻게 잡아야 할까? 프로그래머스의 공식 해설에서는 문제를 다음과 같이 풀이한다.

결론만 요약한다면

금을 우선으로 운반한 경우 금과 은의 양 -> Gmax, Smin

은을 우선으로 운반한 경우 금과 은의 양 -> Gmin, Smax

라고 했을 때,

a <= Gmax

b <= Smax

a + b <= Gmax + Smin = Gmin + Smin

을 만족한다면 주어진 시간 T 안에 a만큼의 금과 b만큼의 은을 운반할 수 있다는 것이다.

 

 

이제 코드를 들여다보겠다.

 

[초기값]

        long answer = (long) (10e9 * 2 * 10e5 * 2);
        int cityLength = g.length;
        long start = 0;
        long end = (long) (10e9 * 2 * 10e5 * 2);

이분탐색이니 start와 end 값에 대한 선언이 필요하다. 이 때 end값의 초기값은 어떻게 될까?

end는 최악의 경우 걸리는 시간으로 이는 ((금의 양)+(은의 양) / (한번에 옮길 수 있는 무게)) * (옮기는데 걸리는 시간 * 2)으로 생각할 수 있다. 이 때 옮기는데 걸리는 시간은 편도 이므로 왕복을 고려해 *2를 한다.

문제의 조건에서 금과 은의 최대값은 각각 10^9이며, 한번에 옮길 수 있는 무게의 최소값은 1, 옮기는데 걸리는 시간의 최대값은 10^5이므로 end는 ((10^9 * 2) / 1) * (10^5 *2)가 된다.

 

[이분탐색 로직]

        while (start <= end) {
            long mid = (start + end) / 2;
            int gold = 0;
            int silver = 0;
            int add = 0;

이분탐색은 while문으로 start <= end인 경우 계속 순회한다.
while 내부적으로 선언된 변수의 역할은 다음과 같다.

mid : 이분탐색의 중간값 (start + end) /2

gold : 운반된 금의 양

silver : 운반된 은의 양

add : 운반된 금과 은의 양

 

 

모든 도시들을 순회하며 금과 은을 운반하는 로직을 수행하는데, 이 때 주의할 점은 주어진 시간 내에 운반할 수 있는 양만큼만 운반한다는 것이다.

            for (int i = 0; i < cityLength; i++) {
                int nowGold = g[i];
                int nowSilver = s[i];
                int nowWeight = w[i];
                long nowTime = t[i];

                long moveCount = mid / (nowTime * 2);
                if (mid % (nowTime * 2) >= t[i]) { // 나머지가 t[i]보다 크거나 같다면 한번 더 움직여야 하므로 +1한다.
                    moveCount++;
                }

                gold += Math.min(nowGold, moveCount * nowWeight);
                silver += Math.min(nowSilver, moveCount * nowWeight);
                add += Math.min(nowGold + nowSilver, moveCount * nowWeight);
            }

주어진 시간인 mid에서 가능한 왕복 횟수를 moveCount로 두고, 현재 도시에서 얻을 수 있는 금과 은을 나타내는 nowGold, nowSilver와 왕복 횟수*운반 가능 무게를 각각 비교하여 최솟값을 운반하도록 한다.

마찬가지로 nowGold + nowSilver와 왕복 횟수*운반 무게 의 최솟값을 add에 더한다.

 

모든 도시 순회가 끝났다면 gold, silver, add에는 주어진 t 시간 안에 운반한 금, 은의 양이 도출된다. 이를 앞서 언급한 조건에 부합하는지 비교한다.

            if (a <= gold && b <= silver && a + b <= add) {
                end = mid - 1;
                answer = Math.min(mid, answer);
                continue;
            }

            start = mid + 1;

성립한다면 주어진 t시간 안에 a, b만큼의 금과 은을 운반가능하다는 이야기이므로 더 적은 시간을 들여서 운반 가능한지 확인한다.

성립하지 않는다면 주어진 t시간 안에는 a, b만큼의 금과 은을 운반할 수 없다는 이야기이므로 더 많은 시간을 들여서 운반 가능한지 확인한다.

 

다른 분들의 풀이를 통해 문제를 이해하긴 했지만, 이런 문제를 실제 테스트에서 마주한다면 여전히 쉽지 않는 문제일 것 같다. 여러 차례의 복기와 유사한 문제를 더 접해볼 필요가 있어보인다.

 

코드

public class Solution {

    public long solution(int a, int b, int[] g, int[] s, int[] w, int[] t) {
        long answer = (long) (10e9 * 2 * 10e5 * 2);

        int cityLength = g.length;
        long start = 0;
        long end = (long) (10e9 * 2 * 10e5 * 2);

        while (start <= end) {
            long mid = (start + end) / 2;
            int gold = 0;
            int silver = 0;
            int add = 0;

            for (int i = 0; i < cityLength; i++) {
                int nowGold = g[i];
                int nowSilver = s[i];
                int nowWeight = w[i];
                long nowTime = t[i];

                long moveCount = mid / (nowTime * 2);
                if (mid % (nowTime * 2) >= t[i]) {
                    moveCount++;
                }

                gold += Math.min(nowGold, moveCount * nowWeight);
                silver += Math.min(nowSilver, moveCount * nowWeight);
                add += Math.min(nowGold + nowSilver, moveCount * nowWeight);
            }

            if (a <= gold && b <= silver && a + b <= add) {
                end = mid - 1;
                answer = Math.min(mid, answer);
                continue;
            }

            start = mid + 1;
        }

        return answer;
    }
}