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

- 링크 : https://programmers.co.kr/learn/courses/30/lessons/86053?language=java 

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

 

- 참고 링크

 https://bladejun.tistory.com/166

프로그래머스 금과 은 운반하기 (python, 파이썬)

 

https://velog.io/@nacean/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EA%B8%88%EA%B3%BC-%EC%9D%80-%EC%9A%B4%EB%B0%98%ED%95%98%EA%B8%B0-C-%ED%92%80%EC%9D%B4

프로그래머스 금과 은 운반하기 C++ 풀이

https://prgms.tistory.com/101

 

https://www.youtube.com/watch?v=MJWtzxi_bsE

 

- 소감 및 풀이

 

 : 3일간 봤는데 모르겠어서 결국 이곳 저곳 찾아보고 문제 풀이를 찾아보았다. 근데 그래도 모르겠어서 또 찾아보고 직접 따라 쳐보고 겨우 이해했다.

 

 : 결정 문제가 나왔다. 

 

결정 문제란?

결정 문제란?

예를 들어 x에 대하여 y로 나누어 떨어지는가? 를 물었을 때

yes or no로 결정될 수 있는 문제

: 결정 문제가 나왔을 시에는 이분 탐색, 파라메트릭 서치을 떠올려 보는 것이 좋다. (필자도 이번에 알게 됨)

 

: 이분 탐색을 활용해 시간을 기준으로 log n 번 안에 필요한 시간을 찾아야 한다.

  그리고 마을 마다 반복문을 돌면서 금을 최대로 캔 경우 무게, 은을 최대로 캔 경우 무게

  를 구하기 때문에 n번이 더 필요하게 된다.

 

 : 따라서 최종 시간 복잡도는 n *log n (여기서 두 번째 n은 T max 시간과 같다)

 

어떠한 시간(T)을 기준으로 운반 되어져야 하는 금, 은을 문제에서 a, b라 했다.

  - a <= G max (T 시간에 금을 최대로 캔 경우)

  - b <= S max (T 시간에 은을 최대로 캔 경우)

  - a + b <= G max + S max (T 시간에 캔 금 최대 개수 + 은 최대 개수)

를 모두 충족 시

 

T 시간에 금, 은을 무조건 캘 수 있게 된다.

 

이유는 풀이 링크들 (https://prgms.tistory.com/101) (https://www.youtube.com/watch?v=MJWtzxi_bsE - 현재는 없어짐!) 에서 찾아 볼 수 있었다.

어떤 시간 T 를 기준으로

금을 최대로 채굴 했을 때(G max) 최대로 가져간 총량(자연스럽게 S min이 됨)

은을 최대로 채굴 했을 때(S max) 최대로 가져간 총량(자연스럽게 G min이 됨)은 같다.

(G와 S는 채굴될 때 이를 어떤 비율로 가져가야하는 제약이 없고 가져갈 수 있는 양은 정해져 있기 때문에)

이는 G와 S의 합의 관계가 기울기가 -1인 선분 처럼 나오게 된다. (아래 그림 참고)

a와 b가 파란색으로 칠한 부분 안에 들어가 있다면

T 시간 안에 원하는 a, b의 양을 채굴 할 수 있음이 성립된다. 

 

예로

필요한 금 a	필요한 은 b
30	80

 

	시간(T) 동안 캘 수 있는 금	시간(T) 동안 캘 수 있는 은	시간(T) 동안 캘 수 있는 최대 총량(G+S)
	70	60	110
	50	70	90
합계	120 (G max)	130 (S max)	200 (G+S)

이라고 했을 때,

 

시간 T 동안 캘 수 있는 총량은 200이고 필요한 금(a)는 30이다.

금 합계가 120이므로 충분히 30을 가져갈 수 있다.

남은 총량(G+S)은 170이고

시간 T 동안 캘 수 있는 은은 130이기 때문에 

필요한 은(b) 80을 가져가는 것은 문제없이 성립하게 된다.

 

 

 

그래서 파라메트릭 서치를 하면서 해당 조건(a <= G max && b <= S max && a+b <= G+S)을

만족하는 최소 시간을 구하는 것이 문제의 답이었다.

 

class Solution {
    public long solution(int a, int b, int[] g, int[] s, int[] w, int[] t) {
        // worst case
        // 2 (금, 은 따로 있을 경우) * 10^9 (채굴 무게 최대) * 2 (왕복 한다면) * 10^5 (도시 개수 최대)
        long end = (long) (Math.pow(10, 14) * 4);
        long start = 0;
        long answer = end;
        
        while (start <= end) {
            long mid = (start + end) / 2;
            
            long goldTotal = 0;
            long silverTotal = 0;
            long gsTotal = 0;
            
            for (int i = 0; i < s.length; i++) {
                long cGold = g[i];
                long cSilver = s[i];
                long cWeight = w[i];
                long cTime = t[i];
                
                long moveCnt = mid / (cTime * 2);
                long restTime = mid % (cTime * 2);
                // 한번 더 편도로 이동 가능
                if (restTime >= cTime) moveCnt++;
                
                // 현재 무게로 현재 시간(mid 시간) 안에 총 가능한 무게
                long cWeightPossibleMax = cWeight * moveCnt;
                goldTotal += (cGold < cWeightPossibleMax) ? cGold : cWeightPossibleMax;
                silverTotal += (cSilver < cWeightPossibleMax) ? cSilver : cWeightPossibleMax;
                gsTotal += (cGold + cSilver < cWeightPossibleMax) ? cGold + cSilver : cWeightPossibleMax;
            }
            
            if (a <= goldTotal && b <= silverTotal && a + b <= gsTotal) {
                // 운반 가능한 시간
                answer = Math.min(mid, answer);
                end = mid - 1;
            } else {
                // 운반 불가능한 시간
                start = mid + 1;
            }
        }
        
        return answer;
    }
}