LEVEL 3 : 금과 은 운반하기

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

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

 

• 문제

  • 

    문제 1

  • 

    예시

  • 문제의 제한조건을 주의하여 보자

 

---

풀이

• 제한 조건을 보게 되면 a, b의 길이는 최대 10^9, 도시 개수 최대 10^5이고, 골드와 실버를 왕복해서 줄 수 있으니 최대 올 수 있는 시간은 10 ^ 9 * 10 ^ 5 * 4이다.
• 따라서 이분 탐색으로 문제를 해결해야한다(파라메트릭 서치) 
  • 이분탐색으로 풀어야 한다는 것을 알았지만 못 풀었다.
  • 핵심은 a+b <= Gold_MAX + Silver_MIN = Gold_MIN + SILVER_MAX = 특정 시간 t에 Silver와 골드를 한 번에
  • 참고 URL : https://prgms.tistory.com/101

  • [월간 코드 챌린지 시즌3] 9월 문제 해설

• 0 <= 시간 < 10 ^ 9 * 10 ^ 5 * 4 이므로 start = 0 , end = 10 ^ 9 * 10 ^ 5 * 4로 설정한다.
• 이분 탐색을 시작
  • Gold_MAX + Silver_MIN의 담을 변수 goldMax
  • Gold_MIN + SILVER_MAX를 담을 변수 silverMax
  • 특정 시간 t에 Silver와 골드를 한 번에
  • 이때, 최대 움직일 수 있는 횟수는 (현재 시간 / 움직이는 시간 * 2)이고(왕복이므로), 마지막은 갔다 돌아올 필요가 없기 때문에, (현재 시간 % 움직이는 시간 * 2)가 가는 시간보다 클 경우 움직일 수 있는 횟수를 하나 추가한다.
  • goldMax에 더해준다.
    • 움직임 횟수 * 운반량 > 해당 도시 gold최대 개수 = 해당 도시 gold 최대 개수를 더해준다.
    • 움직임 횟수 * 운반량 <= 해당 도시 gold최대 개수 =  움직임 횟수 * 운반량을 더해준다.
  • silverMax에 더해준다.
    • 움직임 횟수 * 운반량 > 해당 도시 silver최대 개수 = 해당 도시 silver최대 개수를 더해준다.
    • 움직임 횟수 * 운반량 <= 해당 도시 silver최대 개수 =  움직임 횟수 * 운반량을 더해준다.
  • add에 더해준다.
    • 해당 도시 silver 최대 개수 + 해당 도시 gold 최대갯수 < 움직임 횟수 * 운반량 = 해당 도시 silver 최대갯수 + 해당 도시 gold 최대 개수 를 더해준다.
    • 해당 도시 silver 최대갯수 + 해당 도시 gold 최대갯수 >= 움직임 횟수 * 운반량 = 움직임 횟수 * 운반량을 더해준다.
  • 만약 위의 3가지 조건 중 하나라도 만족하지 못할 경우
    • start = mid +1
  • 모두 만족할 경우 (해당 시간 mid에는 운반이 가능하다)
    • end = mid-1

• public long solution(int a, int b, int[] g, int[] s, int[] w, int[] t) {
  	long answer = (long) Math.pow(10, 9) * (long) Math.pow(10, 5) * 4; //최대 올수 있는 시간 세팅
      long start = 0;
      long end = (long) Math.pow(10, 9) * (long) Math.pow(10, 5) * 4; //최대 올수 있는 시간 세팅
      while(start <= end) { //이분탐색 시작
      	long mid = (start + end) / 2;
          long goldMax = 0;
          long silverMax = 0;
          long add = 0;
          for(int i=0;i<t.length;++i) {
         		long move = mid / (t[i] * 2); //운반 횟수, 왕복이라 시간 * 2이다.
          	if(mid % (t[i] * 2) >= t[i]) { //나머지값이 편행으로 한번 갈수 있을경우
          		move++;//운반을 한번 더 할 수 있다.
          	}
          	goldMax += (g[i] < move * w[i]) ? g[i] : move * w[i]; //해당 마을 최대 운반가능한 gold갯수
          	silverMax += (s[i] < move * w[i]) ? s[i] : move * w[i];//해당 마을 최대 운반가능한 silver갯수
              add += (g[i] + s[i] < move * w[i]) ? g[i] + s[i] : move * w[i]; //해당마을 최대 운반 가능한 gold + silver 갯수
          		
          }
          if(goldMax >= a && silverMax >= b && add >= a + b) { //위 3가지 조건이 모두 만족될때
          	end = mid - 1;  // 해당 시간에는 무조건 가능
              answer = Math.min(mid, answer);
           }else { //해당 시간에는 운반 불가능
           	start = mid + 1;
           }
      }
      return answer;
  }