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

문제 이해하기

어떤 왕국에사 새로운 도시를 건설하기 위해선 금과 은이 필요하다.왕은 새로운 도시를 건설하기 위해서 기존 도시에서 금과 은을 가지고 오려고 하고, 이 광물이 새로운 도시에 도착하기 까지 일정 시간이 소요된다.

새로운 왕국에 필요한 금과 은이 배달되기 까지의 시간을 구하라.

 

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

프로그래머스

 

문제 해결 방법 설명하기

 

1. 경우의 수 계산하기

 왕국 내에 존재할 수 있는 도시의 최대 개수는 10^5까지입니다. 문제를 단순화하여 어떤 왕국에서 광물을 운반할 것인지 여부만 고려하더라도, 2^(10^5)의 경우의 수로 인해 제한된 시간 내에 문제를 해결할 수 없습니다. 따라서 다른 접근 방법이 필요했습니다. 문제를 해결하기 위해 떠오른 아이디어는 주어진 시간 내에 주어진 광물을 배달할 수 있는지의 여부였습니다.

 이때 최대로 주어질 수 있는 시간은 (10^9 * 10^5) * 2로 계산됩니다. 무게 1을 운반하는 데에는 10^5의 시간이 필요하다고 가정하고, 왕복을 고려하여 곱해줍니다. 문제의 최대 계산량을 구하면 log2(10^15 * 2)로 약 50이 되고, 도시의 개수가 10^5임을 고려하여 5,000,000의 연산만으로 문제를 해결할 수 있습니다.

 

2. 이분탐색을 통해서 나를 수 있는 무게 계산하기

이분탐색을 통해서 시간이 주어지면, 주어진 시간에 최대 얼마의 무게를 옮길 수 있을지 게산해야 합니다.

여기서 중요한 점은 자동차가 출발 지점에서 출발하기 때문에, 최초 출발 시에는 화물을 넣어서 출발할 수 있다. 따라서 주어진 시간 내에서 화물차의 마지막 위치가 도착지라면 무게를 한번 더 추가해줘야 합니다.

 

왕복으로 운반하는 경우

편도로 운반하는 경우

 

def solution(a, b, g, s, w, t):
    answer = -1
    start = -1
    end = 10^15 * 2
    
    while start + 1 < end:
        mid = (start + end) // 2   #시간임
        total_gold = 0
        total_silver = 0  
        total = 0
        
        for i in range(len(t)):
            round_trip =  mid // t[i]
            weight = 0
            
            if round_trip % 2 == 0:
                weight += w[i] * (round_trip // 2)
            else:
                weight += w[i] * (round_trip // 2) + w[i]

        if over_weight:
            end = mid
        else:
            start = mid

 

3. 각 도시에서 얼마만큼의 광물을 옮길 것인가 구하기

위에서 우리가 해당 도시에서 옮길 수 있는 무게를 알 수 있다. 여기서 또 중요한 점은 옮길 수 있는 무게는 도시에 있는 광물을 넘어설 수 없다는 점이다. 따라서 우리가 옮길 수 있는 광물의 총 무게가 나오게 된다. 해당 총 무게가 도시를 건설하는데 필요한 광물보다 적다면 시간을 늘리게 된다. 하지만 무게가 더 많다면 시간을 줄 일 수 있게 되는데 여기서 중요한 점은 금과 은의 양이 모두 도시에 필요한 광물보다 많은지 체크해야 한다. 만약 주어진 조건을 만족한다면 시간을 줄일 수 있게 된다.

        for i in range(len(t)):
            round_trip =  mid // t[i]
            weight = 0
            
            if round_trip % 2 == 0:
                weight += w[i] * (round_trip // 2)
            else:
                weight += w[i] * (round_trip // 2) + w[i]
                
            total_gold += min(g[i], weight)
            total_silver += min(s[i], weight)
            total += min(g[i] + s[i], weight)
        
        if a <= total_gold and b <= total_silver and a + b <= total:
            end = mid
        else:
            start = mid

코드

def solution(a, b, g, s, w, t):
    answer = -1
    start = -1
    end = 10**15+1
    
    while start + 1 < end:
        mid = (start + end) // 2   #시간임
        total_gold = 0
        total_silver = 0  
        total = 0
        
        for i in range(len(t)):
            round_trip =  mid // t[i]
            weight = 0
            
            if round_trip % 2 == 0:
                weight += w[i] * (round_trip // 2)
            else:
                weight += w[i] * (round_trip // 2) + w[i]
                
            total_gold += min(g[i], weight)
            total_silver += min(s[i], weight)
            total += min(g[i] + s[i], weight)
        
        if a <= total_gold and b <= total_silver and a + b <= total:
            end = mid
        else:
            start = mid
            
    answer = end
    
    return answer

배운점 정리하기

이런 문제가 parametric search라고 불란다는 점을 알았습니다. parametric search란 최적화 문제를 결정문제로 해결하는 이분탐색을 말한다. 최적화 문제로 이 문제를 정의하면 목표를 만족하는 최소 시간을 구할 수 있는가지만, 결정 문제로 변환하면 x시간에 주어진 목표를 만족할 수 있는가로 변하면서 연산횟수가 현저히 줄어든다.