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

문제

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

접근

1. low는 0, high는 최악의 경우인 10^14 보다 크게 둔다.

2. mid는 금과 은을 운반하는데 주어진 시간으로 둔다.

3. 편도 시간인 t[i]의 값을 time으로 지정을 하면 트럭이 주어진 시간안에 움직이는 횟수는 일단 mid//time*2가 된다.

4. 문제에서 "트럭의 위치는 광물이 있는 마을에 위치한다." 이 말은 편도로 한 번 더 광물을 운반할 수 있다는 뜻이 된다. 즉 왕복하고 남은 시간 (mid % time *2)가 편도(time)보다 크면 한 번 더 광물을 운반할 수 있으므로 move_cnt의 값을 1 올려준다.

5. 각 반복문마다 total_gold, total_silver, total_mineral에 min(최대로 가져갈 수 있는 광물, i번째 마을에 보유하고 있는 광물)을 더해준다.

6. low와 high를 움직이는 조건은 total_gold >= a and total_silver >= b and total_minerals >= a + b이 된다. total_minerals >= a + b를 해줘야하는 이유는 코드에서는 트럭 하나당 총 금과 은을 더하는데 트럭은 동시에 금과 은을 운반하지 않으므로 total_minerals라는 변수를 만들어 필요한 금과 은을 합한 값보다 큰지 확인을 해줘야 한다.

7. 조건을 만족할 경우 answer를 업데이트 하고 high를 줄인다. 만족하지 않은 경우 주어진 시간을 늘리기 위해 low를 늘린다.

Code

def solution(a, b, g, s, w, t):
    def check(mid):
        total_gold, total_silver, total_minerals = 0, 0, 0
        for i in range(len(t)):
            time = t[i]
            round_time = time * 2
            move_cnt = mid // round_time
            if mid % round_time >= time:  # 편도로 갈 수 있는 경우
                move_cnt += 1
            max_take = w[i] * move_cnt

            total_gold += min(max_take, g[i])
            total_silver += min(max_take, s[i])
            total_minerals += min(max_take, g[i] + s[i])

        if total_gold >= a and total_silver >= b and total_minerals >= a + b:
            return True

        return False

    answer = -1
    low, high = 0, 10e15
    answer = high
    while low <= high:
        mid = (low + high) // 2

        if check(mid):
            answer = min(mid, answer)
            high = mid - 1
        else:
            low = mid + 1

    return answer

여담

접근 방법이 도저히 생각이 안나 구글링을 통해 문제를 풀었다.

https://yabmoons.tistory.com/714 를 참고함.