코딩테스트 스터디 - 프로그래머스 금과 은 운반(python)

문제

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

프로그래머스

요약

신도시를 짓기 위해 금 a만큼과 은 b만큼이 필요하다.

여러 도시에 있는 금과 은의 양, 그 도시의 금을 신도시로 운반하는 트럭의 용량과 속도가 주어진다.

도시들에 있는 금과 은을 모아 신도시를 짓기위해 필요한 최소 시간을 구하는 문제다.

의식의 흐름

일단 처음에 봤을 땐 뭔가 수식으로 풀릴 것 같았다.

하지만 머리를 싸매본 결과 도저히 계산을 할 수 없었다.

 

이런 문제는 최소/최대 구하기 문제는 이분탐색을 다음으로 생각하게 된다.

이분 탐색을 하기위해 시간 t가 주어졌을 때, 그 시간 동안 운반을 마칠 수 있는지 확인할 수 있어야한다.

이건 충분히 할 수 있을 거라 생각했다.

처음에 수식으로 풀려고 고민하면서 느꼈지만 간단하게는 안되고, 광물을 모을 수 없는 조건을 찾으면 된다.

각 도시별로 t 시간동안 모을 수 있는 최대 금, 최대 은, 최대 금+은을 다 더해서, 그 양이 필요한 양보다 한 항목이라도 적으면 성공할 수 없다.

구현

자료구조

자료구조를 따로 사용하지 않는다.

알고리즘

시간 t가 주어졌을 때, t시간 동안 필요한 광물을 모을 수 없는지 확인하면 된다.

위에 설명한대로 도시별 최대 금, 은, 금+은을 구해 요구량을 한 항목이라도 충족하지 못하는지 확인하면 된다.

여기서 주의할 점은 트럭이 한 번 나를 때는 이동시간 t[i] 만큼 걸리지만, 그 다음부턴 2*(w[i] -1) 만큼 걸린다는 점이다.

다르게 해석하면 총 시간을 t[i]로 나눈 몫을 2로 나누고 올림을 해주면된다.

 

탐색 범위는 (트럭의 최대 이동시간 10^5) * (금/은의 최대량 10^9) * (금과 은 -> 2) * (왕복 -> 2) = (10&14 * 4) ~ 1이다.

코드

수식으로 풀릴 것 같은데 안풀리고, 주어진 파라미터의 숫자가 매우 크고, 최대/최소를 구하는 문제는

왠만해서 이분탐색으로 풀리는 것 같다.

 

 

'''
	문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/86053
'''

def solution(a, b, g, s, w, t):
    left = 0
    right = 10**14 * 4
    
    while left <= right:
        mid = (left+right)//2
        
        maxgold = 0
        maxsilver = 0
        maxtotal = 0
        for i in range(len(g)):
            moves = (mid // t[i] + 1) // 2
            maxgold += min(g[i], w[i] * moves)
            maxsilver += min(s[i], w[i]  * moves)
            maxtotal += min(g[i] + s[i], w[i] * moves)
        
        if (maxgold >= a and maxsilver>=b and maxtotal>=a+b): #mid 시간내에 배달 가능
            right = mid - 1
        else:
            left = mid + 1
            
    return left