211209 - 금과 은 운반하기

◾ 금과 은 운반하기 : 프로그래머스 LEVEL 3

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

출력

• 금 a kg, 은 b kg을 전달할 수 있는 가장 빠른 시간

입출력 예

a	b	g	s	w	t
10	10	[100]	[100]	[7]	[10]
90	500	[70,70,0]	[0,0,500]	[100,100,2]	[4,8,1]

---

◾ 풀이

1. 해설

• 시간을 기준으로 이분 탐색을 진행한다.
• 특정 시간을 기준으로 각 도시에서 가져올 수 있는 금, 은의 양을 계산한다.
• 가져올 수 있는 금, 은의 양이 기준을 넘어서면 해당 시간을 기준으로 왼쪽 범위를 더 탐색하고, 기준에 못미치면 오른쪽 범위를 더 탐색한다.

---

2. 프로그램

1. start, end 지정
2. mid를 계산하고 해당 시간 기준 계산
3. 가능한 금의 양, 은의 양, 전체 광물의 양 계산
4. a, b를 기준으로 가능한지 확인
5. 가능 여부에 따라 진행
   • 가능한 경우 : end = mid -1로 변경
   • 불가능한 경우 : start = mid + 1로 변경

# 코드
def solution(a, b, g, s, w, t):
    # 최대값으로 지정
    answer = int(1e9 * 1e5 * 2 * 2 - 1e5)
    
    start = 0
    # a = b = 1e9, w = 1, t = 1e5이며
    # 모든 광물이 한 도시에 있는 경우가 최대 시간이며 아래와 같다.
    end = answer

    # 시간을 기준으로 이분 탐색
    while start <= end:
        # mid 내로 가능한지 탐색
        mid = (start + end) // 2

        all_gold, all_silver, all_total = 0, 0, 0
        # mid 시간동안 각 도시에서 가져올 수 있는 금, 은 확인
        for i in range(len(g)):
            now_gold, now_silver, now_total, now_time = g[i], s[i], w[i], t[i]
            if mid // now_time % 2 == 1:
                count = (mid // now_time // 2) + 1
            else:
                count = mid // now_time // 2
            
            all_gold += now_gold if (now_gold < now_total*count) else now_total*count
            all_silver += now_silver if (now_silver < now_total*count) else now_total*count
            all_total += now_gold + now_silver if (now_gold + now_silver < now_total*count) else now_total*count
        # 최대 조건을 만족하는지 확인
        if all_gold >= a and all_silver >= b and all_total >= a+b:
            answer = min(answer, mid)   # answer과 mid 중 최소값 선택
            end = mid -1                # end를 변경하여 재탐색
        else:
            start = mid + 1             # start를 변경하여 재탐색

    return answer