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

1일 1PS 53일차!

📚 문제

---

Level 3

• 이분탐색
• https://min9805.github.io/ps/boj1561/ 해당 문제와 비슷하기에 이분 탐색임을 빠르게 알 수 있었다.

💡 풀이 과정

---

• 시간을 제시하고 해당 시간 안에 금과 은을 모두 전달할 수 있는 지 확인한다.
• end 시간을 제시하기 위해서 각 도시에서 광물을 모두 전달할 때까지 걸리는 최대 시간을 금과 은 별로 구해 더해주었다.
• mid 시간에 금과 은을 모두 전달 가능한 지 살펴보아야 한다.
  • 해당 시간에서 전달 가능한 최대, 최소의 금과 은의 양을 계산한다.
  • a, b 를 최소 금, 은의 양으로 뺴주고 이 중 max 값이 광물의 최대 최소 차보다 작고 (쉽게 말해 a, b 가 최소 금, 은 보다 크고) 부족량의 합이 최대 최소 차보다 작을 경우에 시간이 남는 경우이므로 end = mid
  • a, b 가 최대 금, 은보다 작고 부족량을 채울 수 없을 때 시간이 부족하므로 start = mid + 1 을 진행한다.

📌포인트

---

• [x + y for x, y in fx, fy]
  • 리스트 간의 연산 및 비교 등을 위와 같이 진행할 수 있다.
• [ x / 2 for x in fx]
  • 같은 연산을 리스트에 반복할 때 위 처럼 간단하게 나타낼 수 있다.
• 이분탐색
  • 역시 mid == target 는 진정한 이분 탐색이 아님을 강조한다.

💻 코드

---

def solution(a, b, g, s, w, t):
    start = 1
    end = max(time * (move * 2 + 1) for time, move in zip(t, [gold // weight for gold, weight in zip(g, w)])) + max(time * (move * 2 + 1) for time, move in zip(t, [silver // weight for silver, weight in zip(s, w)]))

    while start < end:
        mid = (start + end) // 2
        move = [((mid // time) + 1) // 2 for time in t]
        move_weight = [ weight * m for weight, m in zip(w, move)]

        min_gold, max_gold, min_silver, max_silver = 0, 0, 0, 0
        for i in range(len(move)):
            if move_weight[i] >= s[i] + g[i]:
                min_gold += g[i]
                max_gold += g[i]
                min_silver += s[i]
                max_silver += s[i]
            else:
                if move_weight[i] <= g[i]:
                    max_gold += move_weight[i]
                elif move_weight[i] > g[i]:
                    max_gold += g[i]
                    min_silver += (move_weight[i] - g[i])

                if move_weight[i] <= s[i]:
                    max_silver += move_weight[i]
                elif move_weight[i] > s[i]:
                    max_silver += s[i]
                    min_gold += (move_weight[i] - s[i])

        dif = max_gold - min_gold
        dif_a = a - min_gold
        dif_b = b - min_silver

        if max(dif_a, dif_b) <= dif and dif >= dif_a + dif_b:
            end = mid
        else:
            start = mid + 1

    return end