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

이환희·2021년 10월 13일

Algorithm

목록 보기

38/47

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의 모든 수의 합

풀이

접근 방법

도무지 어떻게 풀어야 할지 몰라서 해석을 보았다.
이 문제는 이분탐색으로 풀어야 하는 문제이다.
https://yabmoons.tistory.com/714
위 블로그에서 설명을 자세히 해줘 이해할 수 있었다.

문제를 보면 가장 빠른 시간을 구하는 것이다.
1시간 ~ 최악의 시간 까지 모두 구해보면 최소로 걸리는 시간을 구할 수 있을 것이다.

하지만 그렇게 하면 시간이 너무 오래걸린다

따라서 거꾸로 생각해본다.
최악의 시간을 정해 그 시간으로 부터 이분탐색을 하여 최적의 시간을 구하면 되는 것이다.

"시간을 정해놓고, 그 시간내에 필요한 금과 은을 모두 운반할 수 있는지?" 로 문제에 접근

이것이 이분탐색의 핵심이다.

초기값

최악의 시간을 어떻게 정하면 좋을까
간단한 가정을 통해 대략적으로 구할 수 있다.

옮겨야하는 금과 은의 양(A) : 13
한 번에 옮길 수 있는 양(B) : 2
옮기는데 편도로 걸리는 시간(C) : 10
이라 가정한다면,

총 걸리는 시간은
13/2 X (2 X 10) + 10
-> 6번을 옮겨야하고 이때 시간은 왕복 20시간에다가 1번을 편도로 더 옮겨야 하므로 10을 더해줌

따라서 식으로 쓰면
A/B X 2C + (뒤에는 대략적으로만 구하면 돼서 생략)

그러면 문제 제한사항을 보면
A는 10^9 + 10^9
B는 최악이 되려면 1
C는 10^5
이다.
따라서 대략적인 최악의 경우의 시간은

4X 10^14가 된다.

이분탐색

탐색은 다음 두가지를 고려한다.

1. 운송횟수

트럭의 편도 시간: 2초
주어진 시간: 11초
운송횟수는 3번이다.
11/4 -> 두번 왕복하고 3초의 시간이 남는다
편도 시간이 2초이므로 1번 더 갈 수 있다.
만약 주어진 시간이 9초였다면 한 번 더 못갈 것이다.

2. 세 가지 값을 통해 주어진 시간 내에 광물을 옮길 수 있는지 판단

주어진 시간 내에 옮길 수 있는 금의 양
주어진 시간 내에 옮길 수 있는 은의 양
주어진 시간 내에 옮길 수 있는 (금+은)의 양

1번이 a이상이어야 하고
2번이 b이상이어야 하고
3번이 a+b이상이어야 한다.
이 세 가지 조건을 만족해야 하는 범위 내에서 가장 최적값의 시간을 구해내야하는 것이
탐색의 포인트이다.

소스코드

def solution(a, b, g, s, w, t):
    answer = 4*10**14
    start = 0
    end = 4*10**14
    while end>=start:
        mid = (end + start)//2 # 주어진 시간
        gold = 0 # 주어진 시간 내에 옮길 수 있는 금의 양
        silver = 0 # 주어진 시간 내에 옮길 수 있는 은의 양
        add = 0 # 주어진 시간 내에 옮길 수 있는 (금+은)의 양
        for i in range(len(t)):
            now_g = g[i]
            now_s = s[i]
            now_w = w[i]
            now_t = t[i]
            move_cnt = mid//(now_t*2) # 운반 횟수 = 주어진 시간을 왕복 걸리는 시간으로 나눔
            if mid%(now_t*2) >= now_t: # 근데 나머지가 편도 걸리는 시간보다 크면 편도로 한번 더 갈 수 있으므로 운반을 한번 더 할 수 있음
                move_cnt += 1 
            gold += min(now_g, move_cnt*now_w) # 현재 도시의 금량과 최대로 옮길수 있는 광물의 양을 비교해 작은 쪽을 더해줌
            silver += min(now_s, move_cnt*now_w)
            add += min(now_g+now_s, move_cnt*now_w)
        if gold >= a and silver >= b and add >=a+b: # 만약에 a보다 주어진 시간내에 옮길 수 있는 금의 양이 많고, b보다 ..., a+b보다 ... 세 가지 조건을 모두 만족하면 시간을 줄여서 최소값을 찾고
            end = mid - 1
            answer = min(mid, answer)
        else: # 그렇지 않다면 주어진 시간을 늘려라
            start = mid + 1
    return answer