Level 3 금과 은 운반하기 Python 3

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

코딩테스트 연습 - 금과 은 운반하기

 

최종 코드

• Github -> https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level3_금과은운반하기.py

GitHub - hwayeon351/Programmers-Algorithms: 프로그래머스 알고리즘 소스 코드 모음

def solution(a, b, g, s, w, t):
    answer = 0
    left = 0
    right = 10**14*4
    
    while left <= right:
        mid = (left+right)//2
        g_sum, s_sum, total = 0, 0, 0
        for gold, silver, weight, time in zip(g, s, w, t):
            cnt = mid//(time*2)
            if mid % (time*2) >= time: cnt += 1
            
            new_gold = gold if gold <= weight*cnt else weight*cnt 
            new_silver = silver if silver <= weight*cnt else weight*cnt
            g_sum += new_gold
            s_sum += new_silver
            total += new_gold+new_silver if new_gold+new_silver <= weight*cnt else weight*cnt
            
            if g_sum >= a and s_sum >= b and total >= a+b: break
        else:
            left = mid + 1
            continue
        answer = mid
        right = mid - 1
    
    return answer

---

풀이 과정

풀이 시간 1시간 10분

처음에는 그리디 알고리즘을 이용해볼 수 있을까 했는데 다양한 입력에 대한 대응이 어려울 수 있겠다고 판단하게 되었다.

우선 문제는 금 a kg과 은 b kg을 전달할 수 있는 가장 빠른 시간을 구하라고 되어있으며 이때 입력값이 매우 크다.

최악의 경우에는 a = b = 10^9, g = [1], s = [1], w = 1, t = 10^5인 경우를 생각해 볼 수 있다.

그러면 정답은  10^9*10^5*2 + 10^9*(10^5*2-1)이다.

즉, 시간의 범위가 매우 큰데 그 중에서 필요한 금과 은을 전달하는 최소 시간을 구해야하기 때문에 시간에 대한 이분탐색을 적용해 문제를 해결할 수 있었다.

 

mid 시간동안 운반한 금과 은의 각각의 총량을 구해서 a와 b보다 각각 크다면 right 범위를 조정해주고, 그렇지 않다면 left 범위를 조정해주었다.

이때, 주의해야 할 점은 금과 은을 동시에 운반할 수 있는 w를 잘 고려해야 한다.

따라서, 운반한 금과 은의 총량도 따로 구해주고 a+b 이상인 경우에 필요한 만큼 금과 은을 운반할 수 있다는 것을 처리할 수 있었다.

def solution(a, b, g, s, w, t):
    answer = 0
    
    #시간에 대한 이분탐색을 위한 초기값 설정
    # 최악의 경우, a = b = 10^9, g = [1], s = [1], w = [1], t = [10^5]라면 10^9*10^5*2 + 10^9*(10^5*2-1)이 소요된다
    left = 0
    right = 10**14*4
    
    while left <= right:
    	#총 소요 시간을 mid로 가정
        mid = (left+right)//2
        
        #mid 시간동안 운반한 금의 총량, 은의 총량, 금과 은의 총량
        g_sum, s_sum, total = 0, 0, 0
        
        for gold, silver, weight, time in zip(g, s, w, t):
        	#편도 횟수 구하기
            cnt = mid//(time*2)
            if mid % (time*2) >= time: cnt += 1
            
            #현재 도시에서 운반한 금의 양 구하기
            new_gold = gold if gold <= weight*cnt else weight*cnt 
            
            #현재 도시에서 운반한 은의 양 구하기
            new_silver = silver if silver <= weight*cnt else weight*cnt
            
            #총량 더해주기
            g_sum += new_gold
            s_sum += new_silver
            total += new_gold+new_silver if new_gold+new_silver <= weight*cnt else weight*cnt
            
            #필요한 금과 은을 운반한 경우, for문 탈출
            if g_sum >= a and s_sum >= b and total >= a+b: break
            
        #금과 은을 필요한만큼 운반하지 못한 경우, left 값을 조정한다
        else:
            left = mid + 1
            continue
        
        #금과 은을 필요한만큼 운반한 경우, right 값을 조정한다
        answer = mid
        right = mid - 1
    
    return answer
    
 #시간복잡도 = O(n log2 n), 공간복잡도 = O(n)