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

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

프로그래머스

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

 

난이도: LEVEL3

알고리즘 유형: 이분탐색(매개변수 탐색)

 

핵심 부분 

디테일한 end 설정하기  

아무 생각 없이 end를 Long.MAX_VALUE 최댓값으로 설정하고 돌렸는데

5~7개 케이스가 틀렸다. 

 

로직을 보면 충분히 Long.MAX_VALUE를 넘어서는 케이스가 나온다.

// a + b 최댓값:  10^9 * 2 
// 1번 왕복 최대: 10^5 * 2  
// w[i] 최소: 1 
// 최대로 걸리는 시간 2 * 10^9 * 2 * 10^5 = 4 * 10^14

 

 

주어진 시간이 요구로 주어진 금과 은을 챙길 수 있는지 판단

 

처음 문제를 보면 생각이 많아져서 

이번 케이스(도시)에서 어떤 판단으로 금을 어느 정도 챙기고 은을 어떻게 챙기지 이런 생각이 엄청 들었다. 

하지만 몇 가지 조건으로 판단이 가능하다는 생각이 떠올랐다. 

 

totalSum을 통해서 매 도시마다 최대로 챙겨갈 수 있는 무게를 누적

totalA을 통해서 매 도시마다 최대로 챙겨갈 수 있는 금 무게를 누적 

totalB을 통해서 매 도시마다 최대로 챙겨갈 수 있는 은 무게를 누적 

 

totalSum >= A + B 

totalA >= A

totalB >= B 

 

3가지 조건이 모두 맞으면 이번 시간에 가능!

 

왜 이 3가지 조건이 맞으면 가능한걸까?

 

어떤 시간 t초에 금, 은 운반이 모두 가능하다면 아래 3가지 조건이 맞을까를 생각해 본다. 

totalSum >= A + B 

totalA >= A

totalB >= B 

 

통과 케이스 

t초에 금과 은을 모두 가져가야 하니까 당연히 totalSum >= A + B 

t초에 금을 모두 가져가야 하니까 totalA >= A

t초에 은을 모두 가져가야 하니까 totalB >= B 

 

실패 케이스 

만약 totalSum < A + B 라면 

totalA >= A

totalB >= B 

2가지 조건에 해당 하더라도 

어떤 도시에서 금이나 은을 더 운반하는데 더 시간 소요했어야 하는구나를 상상? 할 수 있다. 

 

이렇게 간단한 조건식으로 언제 금이나 은을 얼마큼 챙겨야 하는지 복잡한 로직 없이 판단이 가능하다. 

이런 부분이 참 어렵다;;

 

정답 코드 

import java.util.*;
class Solution {
    static int A, B, size;
    static int [] G; static int [] S; static int [] W; static int [] T;
    
    public long solution(int a, int b, int[] g, int[] s, int[] w, int[] t) {
        A = a; B =b; G = g; S = s; W = w; T = t; size = s.length;
        
        // 10^9 * 2 = a + b 최댓값 
        // 1번 왕복 최대 10^5 * 2  
        // w[i] 최소: 1 
        // 최대로 걸리는 시간 2 * 10^9 * 2 * 10^5 = 4 * 10^14 
          
        long start = 0;
        long end   = (long) Math.pow(10, 14) * 4;
        while(start < end){
            long mid = (start + end) / 2;
            if(check(mid)){
                end = mid;
            }
            else start = mid + 1;
        }
        return start;
    }
    public boolean check(long time){
        long totalSum = 0;
        long totalA   = 0;
        long totalB   = 0;
        for(int i = 0; i < size; i++){
            long count = time / (2L * T[i]);
            if(time % (2L * T[i]) >= T[i]){ // 편도 시간이 남았다면 
                count++;
            }
            long sum = count * W[i]; // 가져갈 수 있는 총 무게 
            totalSum += Math.min(sum, G[i] + S[i]);
            totalA   += Math.min(sum, G[i]); // 금 최대로 
            totalB   += Math.min(sum, S[i]); // 은 최대로 
            if(totalSum >= A + B && totalA >= A && totalB >= B) return true;
        }
        if(totalSum < A + B) return false;
        if(totalA < A) return false;
        if(totalB < B) return false;
        
        return true;
    }
}