[프로그래머스] 금과 은 운반하기 - JAVA

프로그래머스 코딩 테스트 연습 문제 -  금과 은 운반하기 / JAVA 풀이 정리

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

프로그래머스

---

풀이 방법

1. 각 도시에 대해 금과 은을 운반할 수 있는 최적의 경로를 선택
2. 선택된 경로에서 건설 장소로 이동하고, 금과 은을 운반하며 최소 시간을 계산
3. 이진 탐색으로 각 도시에 대해 최소 시간을 계산하고, 그중 최소 시간을 반환

---

코드 풀이

매개변수(Parameter) 설명

• a : 건설할 도시에 전달해야 할 금의 무게
• b : 건설할 도시에 전달해야 할 은의 무게
• g : 각 도시에서 보유한 금의 무게
• s : 각 도시에서 보유한 은의 무게
• w : 각 도시의 트럭이 운반 가능한 최대 무게
• t : 각 트럭이 편도 이동에 걸리는 시간 

운반 가능 여부 메서드

먼저, 각 도시의 트럭이 이동하며 최대로 운반할 수 있는 광물의 무게를 계산하고, 운반해야 하는 무게를 충족하는지 여부를 반환하는 메서드를 작성한다.

전체코드 ↓

public boolean isPossible(long time, int a, int b, int[] g, int[] s, int[] w, int[] t) {
        int numCities = g.length;
        long totalOre = 0L;
        long totalGold = 0L;
        long totalSilver = 0L;

        for (int i = 0; i < numCities; i++) {
            long trips = time / (2L * t[i]);
            if (time % (2L * t[i]) >= t[i]) trips++;

            // 해당 시간에 옮길 수 있는 무게
            long tsptableWeight = Math.min(trips * w[i], g[i] + s[i]);
            // 각 도시의 총합 최대 무게 누적
            totalOre += tsptableWeight;
            totalGold += Math.min(tsptableWeight, g[i]);
            totalSilver += Math.min(tsptableWeight, s[i]);
        }


        return (totalOre >= a + b) && (totalGold >= a) && (totalSilver >= b);
    }

 

public boolean isPossible(long time, int a, int b, int[] g, int[] s, int[] w, int[] t) {
        int countCities = g.length;
        long totalOre = 0L;
        long totalGold = 0L;
        long totalSilver = 0L;

        for (int i = 0; i < countCities; i++) {
            long trips = time / (2L * t[i]);
            if (time % (2L * t[i]) >= t[i]) trips++;

주어진 time값을 왕복 운행 소요 시간(2L * t [i])로 나눈 값을 trips(트럭이 운반해야하는 횟수)으로 계산한다.

time을 왕복 소요 시간으로 나눈 나머지가 편도 소요 시간(t [i])보다 크거나 같다면, 한번 더 운행해야 하므로 trips를 증가시킨다.

// 위에서 이어짐

		// 해당 시간에 옮길 수 있는 무게
            long tsptableWeight = Math.min(trips * w[i], g[i] + s[i]);
            // 각 도시의 총합 최대 무게 누적
            totalOre += tsptableWeight;
            totalGold += Math.min(tsptableWeight, g[i]);
            totalSilver += Math.min(tsptableWeight, s[i]);
        }

이렇게 계산한 운행동안 최대로 옮길 수 있는 무게(trips 값에 트럭이 운반할 수 있는 무게 w를 곱한 값)와, 도시에 필요한 금과 은을 합한 값 중 최솟값으로 tsptableWeight 값을 설정하고, 총 금속 무게에 합산해준다.

총 금 무게와 은 무게에도 이 값과 도시에 필요한 금과 은의 값을 비교해 최솟값을 합산해 준다.

 

return (totalOre >= a + b) && (totalGold >= a) && (totalSilver >= b);

 

총 광물 무게가 건설할 도시에 전달해야 하는 금과 은을 합한 무게를 충족하면서, 금과 은의 각 무게도 충족되는지 확인해 충족한다면 true, 아니라면 false를 반환한다.

---

최적 시간 탐색 메서드

위 메서드를 통해 이진 탐색을 수행하여 최적의 시간을 찾아내는 메서드를 작성한다.

public long solution(int a, int b, int[] g, int[] s, int[] w, int[] t) {
        long highTime = 400000000000000L;
        long lowTime = 0;

        // 이진 탐색
        while (lowTime + 1 < highTime) {
            long midTime = (lowTime + highTime) / 2;

            if (isPossible(midTime, a, b, g, s, w, t)) {
            	highTime = midTime;
            }
            else lowTime = midTime;
        }
        return highTime;
    }

탐색 구간을 설정하고, 최적 시간을 찾을 때까지 이진 탐색을 수행한다.

isPossible 메서드를 통해 최적 시간이 중간값의 앞에 있는지, 뒤에 있는지를 확인한다.

---

https://seongho-jo-5.tistory.com/22

[알고리즘] 이진 탐색(Binary Search)