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

문제 링크

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

프로그래머스

 

 

 

 

코딩테스트 연습 > 월간 코드 챌린지 시즌3 > 금과 은 운반하기

 

 

 

문제 설명

 

 

어느 왕국에 하나 이상의 도시들이 있습니다. 왕국의 왕은 새 도시를 짓기로 결정하였습니다. 해당 도시를 짓기 위해서는 도시를 짓는 장소에 금 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 해야 합니다.

 

 

 

 

 

 

나의 코드

// 이분탐색 알고리즘을 알아도 (Gmax = 골드 우선 탐색 , Smax = 실버 우선 탐색) 이라고 했을 때 
// a <= Gmax, b <= Smax, a + b <= Gmax + Smin = Gmin + Smax = add 라면 
// 주어진 시간 T 안에 a만큼의 금과 b만큼의 은을 운반 할 수 있다 라는걸 알기 어려운 문제였다.
class Solution {
    public long solution(int a, int b, int[] g, int[] s, int[] w, int[] t) {
        long answer = -1;
        
        // target => 시간
        long start = 0;
        long end = (long) (((10e9 + 10e9) / 1) * (10e5 * 2)); // 최대 시간 ((금의 양 + 은의 양) / 한 번에 운반 가능한 트럭의 최소 무게) * (옮기는데 걸리는 시간 * 2)
        
        while(start <= end) {
            long mid = (start + end) / 2;
            long gold = 0; // 특정 시간 동안 얻을 수 있는 최대 골드 수
            long silver = 0; // 특정 시간 동안 얻을 수 있는 최대 실버 수
            long add = 0; // 특정 시간 동안 골드와 실버를 한 번에 얻을 수 있는 최대 수
            // 이 세가지 값을 가지고 a <= Gmax, b <= Smax, a + b <= Gmax + Smin = Gmin + Smax = add 를 만족한다면 현재 T라는 시간은 a, b를 운반할 수 있다를 결정할 수 있게 된다.
            
            for(int i=0; i<t.length; i++) {
                long cnt = mid / t[i]; // 해당 시간까지 해당 도시에서 운반 할 수 있는 횟수
                if(cnt % 2 == 0)
                    cnt /= 2;
                else
                    cnt = cnt / 2 + 1;
            
                gold += Math.min(g[i], cnt * w[i]);
                silver += Math.min(s[i], cnt * w[i]);
                add += Math.min(g[i] + s[i], cnt * w[i]);
            }
               
            // a <= Gmax, b <= Smax, a + b <= Gmax + Smin = Gmin + Smax = add 라면 mid 시간 안에 가능
            if(gold >= a && silver >= b && add >= a + b) {
                end = mid - 1; // 더 최적의 시간 탐색
                answer = mid;
            } else {
                start = mid + 1; // 시간을 늘려 다시 탐색
            }
        }
        
        return answer;
    }
}

 

풀이

1. 운반 가능한 시간을 찾기 위해서는 T라는 시간의 범위가 매우 크므로 이분 탐색(Binary Search)을 이용해야 한다.
2. 이분 탐색을 이용해야 하는 것까지는 알 수 있지만 어떤 조건을 만족해야 운반 가능한 시간인지를 판별할 수 있는지는 어려운 문제였다. 결국 다른 풀이을 참고하여 만족 조건을 참고하였다.
3. 판별 조건을 보면 다음과 같다. 
   1. 제한 시간 안에 금을 최우선적으로 운반했을 때 운반할 수 있는 금의 양과 은의 양을 각각 Gmax, Smin 이라고 정의합니다.
   2. 제한 시간 안에 은을 최우선적으로 운반했을 때 운반할 수 있는 금의 양과 은의 양을 각각 Gmin, Smax 이라고 정의합니다.
   3. 그렇다면 Gmax + Smin = Gmin + Smax 입니다.
   4. 만약 a ≤ Gmax, b ≤ Smax 그리고 a + b ≤ Gmax + Smin = Gmin + Smax = add라면, 주어진 시간 T 안에 a만큼의 금과 b만큼의 은을 운반할 수 있습니다.
4. 이제 판별 조건을 알았으니 이분 탐색을 이용하여 해당 조건을 만족하는지 확인하고 최적의 시간을 탐색하면 된다.
5. target을 시간으로 하고 최소의 시간(start)을 0으로 최악의 시간(end)을 ((10e9 + 10e9) / 1) * (10e5 * 2)으로 초기화 한다. 수가 크므로 long형으로 선언한다.
   ( (금의 최대 양(10^9) + 은의 최대 양(10^9)) / 한 번에 운반 가능한 트럭의 최소 무게(1) * (옮기는데 걸리는 시간(10^5) * 왕복(2)) )
6. 이제 start가 end보다 커질 때까지 while문을 반복하면서 조건을 만족하는 최적의 시간을 구하면 된다.
7. start와 end를 더하고 2로 나눈 값을 mid에 저장하고 해당 mid의 시간동안 얻을 수 있는 최대 골드 수를 저장할 gold와 해당 mid의 시간동안 얻을 수 있는 최대 실버 수를 저장 할 silver와 해당 mid의 시간동안 골드와 실버를 한 번에 얻을 수 있는 최대 수를 저장할 add를 0으로 초기화 한다.
8. 이제 t는 해당 마을에서 도시로 편도로 이동하는데 걸리는 시간이므로  t의 길이가 곧 마을의 개수이므로 t를 순회한다. mid를 t[i]로 나눈 수 cnt가 해당 도시에서 mid의 시간동안 새 도시까지 편도로 이동 가능한 횟수이므로 cnt를 2로 나누어 왕복 운행으로 운행하게 한다. cnt를 2로 나눈 나머지가 1이라면 마지막에는 편도로 한 번 더 갈 수 있으므로 1회 운행을 추가하도록 한다.
9. 해당 도시에서 새 도시로 트럭을 운행할 수 있는 횟수 cnt를 알았으니 glod, silver, add를 구하도록 한다.
   운행할 수 있는 횟수(cnt) * 한 번에 운반 할 수 있는 무게(w[i])의 값을 gold와 silver에 추가시켜주면 되는데 해당 도시의 광물이 cnt * w[i] 만큼 충분하지 않을 수 있기 때문에 cnt * w[i] 와 해당 광물(g[i] 또는 s[i])과 비교하여 작은 값을 해당 광물(gold 또는 silver)에 더해주도록 한다. 그리고 두 광물을 더한 g[i] + s[i] 와 cnt * w[i] 를 비교하여 작은 값을 add에 더해주도록 한다.
10. 이렇게 t를 순회하면서 gold, silver, add를 구했으면 이 세가지 값을 가지고 판별 조건(a <= Gmax, b <= Smax, a + b <= Gmax + Smin = Gmin + Smax = add)을 만족하는지 확인하면 된다.
11. 따라서 gold가 a 이상이고 silver가 b 이상이고 add가 a + b 이상이라면 answer에 mid를 저장하고 end를 mid - 1로 변경하여 시간을 줄여 더 최적의 시간을 탐색하고 조건을 만족하지 못한다면 start를 mid + 1로 변경하여 시간을 늘려 다시 탐색하도록 한다.
12. 이렇게 while문을 반복하다 start가 end보다 커지면 while문을 종료하고 최적의 시간이 저장되어 있는 answer를 반환한다.  

 

 

참고
https://prgms.tistory.com/101
https://yabmoons.tistory.com/714
https://redbinalgorithm.tistory.com/696