[PS] 금과 은 운반하기

Byeonggwan Kang·2023년 10월 18일

목록 보기

2/10

https://school.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 ≤ 10^9
1 ≤ g의 길이 = s의 길이 = w의 길이 = t의 길이 = 도시 개수 ≤ 10^5
0 ≤ g[i], s[i] ≤ 10^9
1 ≤ w[i] ≤ 10^9
1 ≤ t[i] ≤ 10^5
a ≤ g의 모든 수의 합
b ≤ s의 모든 수의 합

문제 해결 방법

완전 탐색시 n시간마다 도시에서 가져올 수 있는 광물의 양을 계산해 나갈 수 있다.

하지만 최악의 상황에 1시간마다 모든 도시를 탐색해야 하므로 대충 10^9 * 10^5 = 10^14 이상의 명령을 내릴 시간이 필요하다.

내가 정한 기준에 따르면 이 값을 1억(10^8) 아래로 내려야 보통의 알고리즘 문제에서 통과할 수 있다.

dp는 공간이 부족하다는 것도 알 수 있다. 다음은 어떤 알고리즘을 생각할 수 있을까?

이런 문제에선 보통 이분탐색을 사용할 수 있다.

이분탐색을 써서 풀 수 있는 문제의 조건? 모습?은 다음과 같다.

탐색시 터무니없는 시간이나 공간 복잡도를 요구한다.
어떤 값(이분탐색의 대상이 되는 값)을 정답 기준으로 조절함에 따라서 조건을 만족하거나 불만족한다.

이 문제는 첫 번째 조건을 만족한다는 것을 알 수 있다.

그리고 이 문제에서 필요한 시간을 t라고 하면, t 이상일 땐 광물을 요구치만큼 가져온다는 조건을 만족하고 t 미만일 땐 그 조건을 불만족한다.

이분탐색을 사용할 땐 위처럼 '광물치를 요구치만큼 가져올 수 있냐'와 같은 조건을 사용해서 mid값을 조절한다.

t 시간동안 가져올 수 있는 광물의 양은 어떻게 계산해야할까?

각 도시마다 t 시간동안 가져올 수 있는 금+은의 총 합이 광물의 요구치 이상이여야 한다.

이 경우 금, 은이 모든 도시에 넉넉할 경우 답이 된다.

모든 도시에서 가져올 수 있는 광물의 총 합을 알면 잘 조절해서 가져왔을때 조건을 만족한다.

근데 이러면 도시마다 금, 은이 불균형한 경우를 답으로 찾지 못한다.

예를 들어 2개의 도시에서 금을 1씩 가져올 수 있고 양쪽에 100 씩 있다면 100번만 왔다 갔다 할 시간만 있어도 되지만, 한쪽에 50 다른 한쪽에 150 있는 경우 150번을 왔다갔다 해야만 한다.

따라서 두 개의 조건이 더 필요하다.

각 도시마다 t 시간동안 가져올 수 있는 금의 총 합이 필요한 금의 양 이상이여야 한다.
각 도시마다 t 시간동안 가져올 수 있는 은의 총 합이 필요한 은의 양 이상이여야 한다.

사실상 이 조건을 찾는 것이 이분탐색의 전부이다.

코드 구현

def solution(a, b, g, s, w, t):
    answer = -1
    low = 0
    high = 10000000000000000
    
    while low <= high:
        mid = (low + high) // 2
        gSum = 0
        sSum = 0
        gsSum = 0
        # 계산
        
        for i in range(len(g)):
        	# mid // t[i] 는 트럭이 편도로 이동한 횟수
            count = (mid // t[i] + 1) // 2
            
            gSum += w[i] * count if w[i] * count <= g[i] else g[i]
            sSum += w[i] * count if w[i] * count <= s[i] else s[i]
            gsSum += w[i] * count if w[i] * count <= g[i] + s[i] else g[i] + s[i]
            
        if gSum < a or sSum < b or gsSum < a+b:
            low = mid + 1
        else:
            answer = mid
            high = mid - 1
        
    return answer