프로그래머스 금과 은 운반하기 (python, 파이썬)

• 문제

어느 왕국에 하나 이상의 도시들이 있습니다. 왕국의 왕은 새 도시를 짓기로 결정하였습니다. 해당 도시를 짓기 위해서는 도시를 짓는 장소에 금 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^2
    • 1 ≤ t[i] ≤ 10^5
    • a ≤ g의 모든 수의 합
    • b ≤ s의 모든 수의 합

---

• 입/출력

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

---

• 코드

def solution(a, b, g, s, w, t):
    answer = (10**9) * (10**5) * 4
    
    start = 0
    # 최악의 경우
    # 걸리는 최소시간(왕복) : 2 
    # 금 따로 은 따로(한도시에 금,은만 있을경우) : 2
    # 광물의 최대무게 : 10**9
    # 도시의 최대개수 : 10**5
    end = (10**9) * (10**5) * 4
    
    while start <= end:
        mid = (start + end) // 2
        gold = 0
        silver = 0 
        total = 0
        
        for i in range(len(g)):
            # 현재 정보
            now_gold = g[i]
            now_silver = s[i]
            now_weight = w[i]
            now_time = t[i]
            
            # 주어진 시간내에서 이동할 수 있는 횟수(왕복으로 계산)
            move_cnt = mid // (now_time * 2)
            
            # 편도 추가
            if mid % (now_time * 2) >= now_time:
                move_cnt += 1
                
            gold += now_gold if (now_gold < move_cnt * now_weight) else move_cnt * now_weight 
            silver += now_silver if (now_silver < move_cnt * now_weight) else move_cnt * now_weight
            total += now_gold + now_silver if (now_gold + now_silver < move_cnt * now_weight) else move_cnt * now_weight 
        
        if gold >= a and silver >= b and total >= a + b:
            end = mid - 1
            answer = min(answer, mid)
        else:
            start = mid + 1
        
    return answer

단순 탐색으로 풀기엔 최악의 경우를 생각해보면 시간이 너무 오래걸려서 진행할 수 없다.

 

시간을 기준으로 이분탐색해줘서 푸는게 포인트이다.

 

move_cnt는 움직일수는 총 횟수이다. 편도로 시간이 나와있기 때문에 한 번 운반하고 갔다오면 시간의 2배를 해주어야한다. 그러나 마지막 배달의 경우 편도로 운반해서 다 채우면 다시 돌아올 필요가없기때문에 한 번 갈수있는 시간까지 남으면 +1을 진행해주는것이다.

 

이후 move_cnt(운반횟수) * now_weight(한번에 옮길수있는 무게)를 계산하면 총 운반할수있는 양이 계산된다.

만약 A마을의 금의 무게가 한번에 운반할 수있는 양보다 적으면 금의 무게를 더해주고 아니라면 운반 가능한 양을 더해주는것이다. 은도 금과 마찬가지이다.

 

단, 여기서 주의해야할 점은 for문한번으로 금과 은의 무게를 나르지만 둘의 무게를 더한것이 한번에 나를 수 있는 제한보다 큰지 확인을 해주어야한다. 금과 은의 무게를 나르는것이 한번에 나를 수 있는 양보다 크면 한번에 나를 수 있는 양을 전체무게로 정해준다.

 

마지막에 금의 무게와 은의 무게 그리고 total의 무게가 각각의 기준보다 큰지 확인하고 

start와 end를 조절해준다.(이분탐색에 대해서 잘 모르시면 이분탐색 기초문제 백준에 많이 있으니 한 번 풀어보세요!)

---

• 출처

https://programmers.co.kr/learn/courses/30/lessons/86053?language=python3