프로그래머스 금과 은 운반하기 Kotlin (이분탐색)

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/86053

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

문제 설명

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

---

입출력 예

---

입출력 예 설명

입출력 예 #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 해야 합니다.

풀이

월코챌 해설 : https://prgms.tistory.com/101?category=882795 

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

킹갓 고릴라 호석님의 도움을 받아서 풀었다.

9월 월코챌에 나온 파라메트릭 서치 문제이다.

당시에는 파라메트릭 서치를 몰라서 풀지 못했는데,

최근 파라메트릭 유형이 종종 코테에 나오는 것 같아 공부했고,

이 문제는 내가 풀어본 파라메트릭 문제 중 유일하게 어렵다고 생각한 문제이다.

 

파라메트릭 서치는 기존 이분 탐색과 크게 다르지 않지만,

mid가 답이 될 수 있는지 체크하는 과정이 쉽냐 어렵냐에 따라 난이도가 갈리는 것 같다.

 

개인적으로 이 문제는 mid가 답인지 체크하는 과정이 어려웠다고 생각한다.

 

이분 탐색의 mid는 시간을 가리킨다.

여기서 end는 운반 시간의 상한선이다. 

금의 최대량은 10e9, 은의 최대량도 10e9

운반 시간의 최대는 10e5

운반 가능한 트럭의 최소 무게는 1

왕복하면 *2

즉, 금을 (10e9/1번 + 은을 10e9/1번) * 10e5 * 2로,

운반 시간의 상한선은 10e9 * 2 * 10e5 * 2가 된다.

 

이렇게 이분 탐색을 설정하고, 이젠 mid시간 내에 금과 은을 a,b이상 운반할 수 있는지 검사하고,

운반할 수 있다면 mid를 줄여나간다.

이 부분은 아래 코드의 주석을 참고하자...

 

다만, 이 부분은 이해가 잘 되지 않을 것이다.

왜냐면, 내가 왜 조건이 이렇게 되는지 이해를 못 했었다.

        if(tot>=(a+b).toLong() && gCarry>=a && sCarry>=b){
            //println("${tot} $gCarry $sCarry")
            return true
        }

만약 금 + 은의 운반 가능한 토탈 양이 21이라고 하고,

금의 운반 가능한 토탈 양이 15

은의 운반 가능한 토탈 양이 18이라 하자.

예제 1에서 금은 최소 10만큼 운반해야 하고, 은도 최소 10만큼 운반해야 한다.

금을 최소 10만큼 운반한다 하면, 금+은의 운반 가능한 토탈 양 21에서 10을 빼,

은의 운반 가능한 토탈 양은 11만큼 남는다.

이 경우, 은의 운반 가능한 토탈 양은 18이었지만, 금에서 10만큼 운반했기 때문에 은의 운반 가능한 토탈 양은 11이 된다.

은도 최소 10만큼 운반해야 하는데, 최대 11만큼 운반할 수 있기 때문에, 위의 조건식이 성립된다.

 

 

코드

import kotlin.math.*
class Solution {
    
    fun check(mid : Long, a : Int, b : Int, g : IntArray, s : IntArray, w : IntArray, t : IntArray ):Boolean{
        
        var tot=0L
        var gCarry=0L
        var sCarry=0L
        for(i in w.indices){
            //전체 시간을 한 번 왕복하는 시간으로 나누면 운반 가능 횟수
            var cnt : Long = mid / (t[i]*2)
            //편도로 한 번 더 갈 수 있는 경우 1추가
            if(mid%(t[i]*2)>=t[i]) cnt++
            //금+은 한 번에 이동 가능한 최대 운반량은 트럭 한 번 운반 무게 * 운반 횟수 vs 금 + 은 최대량
            val maxCarry : Long = min(cnt*w[i], (g[i]+s[i]).toLong())    
            //금 운반 최대량은 각 도시의 (금 최대량 vs 최대 운반량) 누적
            gCarry += min(g[i].toLong(),maxCarry)
            //은 운반 최대량은 각 도시의 (은 최대량 vs 최대 운반량) 누적
            sCarry += min(s[i].toLong(),maxCarry)
            //금+은 최대 운반량
            tot+=maxCarry
        }
        
        if(tot>=(a+b).toLong() && gCarry>=a && sCarry>=b){
            //println("${tot} $gCarry $sCarry")
            return true
        }
        return false
        
    }
    
    fun solution(a: Int, b: Int, g: IntArray, s: IntArray, w: IntArray, t: IntArray): Long {
        
        //시간 기준으로 이분 탐색
        //mid(시간)안에 운반 가능한지
        
        var start = 1L
        var end = 400000000000000L
        while(start<end){
            val mid : Long = (start+end)/2
            if(check(mid,a,b,g,s,w,t)){
                end=mid 
            }
            else{
                start=mid+1
            }
        }
        return end
    }
}