[프로그래머스(Programmers)][자바(java)] (Lv3) 금과 은 운반하기 <월간코드챌린지3>

 

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

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

 

문제 접근

 

https://prgms.tistory.com/101

월간 코드 챌린지 시즌3 9월 해설

-   결정 문제로 환원
 =>  시간 T가 주어졌을 때, T라는 시간 안에 트럭을 최대한 활용시켜 금과 은을 각각 a, b만큼 운반할 수 있는지 판별하는 문제
-  이분 탐색 활용  ( 시간 T를 최소값과 최대값 사이의 중간값으로 지정 )
-  1.  제한 시간 안에 금을 최우선적으로 운반했을 때 운반할 수 있는 금의 양과 은의 양을 각각 G_max, S_min이라고 정의
   2.  제한 시간 안에 은을 최우선적으로 운반했을 때 운반할 수 있는 금의 양과 은의 양을 각각 G_min, S_max이라고 정의
   3.  G_max + S_min  =  G_min + S_max
   4.  a <= G_max,
        b <= S_max,
        a+b <= G_max + S_min = G_min + S_max
       라면 주어진 시간 T 안에 a만큼의 금과 b만큼의 은 운반 가능

 

문제 풀이

 

public class Solution {
	
	public long solution(int a, int b, int[] g, int[] s, int[] w, int[] t) {
		final long max = (long)(1e9 * 2 * 1e5 * 2);
		long l = 0, r = max, T, ans = max; int n = s.length, i; // left, right, mid(T:time)
		long gm, sm, gsm, gc, sc, wc, tc, rc, wt, ab = a + b, gsc;
		// gold/silver/g+s_max, gold/silver/weight/time_current, round_trip_cnt, wgight_total, a+b, g+s_current
		while (l <= r) {
			T = (l + r) / 2;
			gm = sm = gsm = 0;
			for (i = 0; i < n; i++) {
				gc = g[i]; sc = s[i]; wc = w[i]; tc = t[i]; gsc = gc + sc;
				rc = (long)Math.ceil((double)(T / tc) / 2); // (왕복 횟수) = ceil( ( (총 소요 시간) / (한 번 운반 시 소요 시간) ) / 2 )
				wt = rc * wc; // (총 광물의 무게) = (왕복 횟수) * (한 번에 운반 가능한 광물 최대 무게)
				gm += Math.min(gc, wt);
				sm += Math.min(sc, wt);
				gsm += Math.min(gsc, wt);
			}
			if (a <= gm && b <= sm && ab <= gsm) {
				r = T - 1;
				ans = T;
			} else
				l = T + 1;
		}
		return ans;
	}
}

 

-  새로운 도시를 건설하기 위해 금 a kg과 은 b kg을 전달 시 소요 시간을 T라고 할 때, 
   T는 이분 탐색으로 최소 시간( l : left, 초기값은 0 ), 최대 시간( r : right, 초기 값은 1e9*2*1e5*2 )의 중간 값으로 지정
-  a <= g_max, b <= s_max, a+b <= g_max + s_min = g_min + s_max 의 조건을 만족해야 하므로
   각 도시에서 운반한 총 금( g )과 은( s )의 무게, 그것을 모두 합한 gm, sm, gsm( gm : gold_max, sm : silver_max, gsm : g+s_max )을 구해야 함
-  각 도시에서 운반한 총 금의 무게( g )는
   ( 한 번 운반 시 최대 광물 무게( wc : weight_current ) x 왕복 횟수( rc : round_trip_count ) )와
   가지고 있는 금의 무게( gc : gold_current ) 중 더 작은 값이 됨
-  각 도시에서 운반한 총 은의 무게( s )는
   ( 한 번 운반 시 최대 광물 무게( wc ) x 왕복 횟수( rc ) )와 가지고 있는 은( sc : silver_current )의 무게 중 더 작은 값이 됨
-  각 도시에서 운반한 총 금과 은의 무게( gs )는
   ( 한 번 운반 시 최대 광물 무게( wc ) x 왕복 횟수( rc ) )와 가지고 있는 금+은의 무게( gsc : g+s_current ) 중 더 작은 값이 됨