[프로그래머스] 금과 은

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

프로그래머스

🤔 문제분석

주어진 입력값이 상당히 크다면 이분탐색을 의심했어야했는데, 다른 방식으로 문제를 해결하려고 한참 해맸던 문제입니다.

시간을 기준으로 이분탐색을 하는데 해당 시간에 모든 금과, 은을 가져다 놓을 수 있는지 없는지 확인합니다.

1. 금과 은을 모두 나를 수 있다면 시간을 좁혀 탐색해봅니다.
2. 금과 은을 모두 나를 수 없다면 시간을 늘려 탐색해봅니다.

💻 코드

# <https://school.programmers.co.kr/learn/courses/30/lessons/86053>

# 시간을 기준으로 이분탐색한다.
import sys

def solution(a, b, g, s, w, t):
    # 도시의 개수
    n = len(g)
    start = 1
    end = sys.maxsize
    answer = sys.maxsize
    
    while end >= start:
        mid = (start+end) // 2
        total = 0
        g_total = 0
        s_total = 0
        
        for i in range(n):
            # 해당시간에 옮길 수 있는 횟수
            cnt = mid // (t[i]*2)
            
            # 편도로 갔다와야하는경우의 수 추가
            if mid % (t[i]*2) >= t[i]:
                cnt += 1
            
            # 시간내에 옮길 수 있는 최대 무게
            tmp = w[i] * cnt
            
            total += min(tmp, g[i] + s[i])
            g_total += min(tmp, g[i])
            s_total += min(tmp, s[i])
        
        # 옮길 수 있는지 확인 없다면 시간을 늘린다 그렇지 않다면 시간을 줄여본다.
        if total >= a+b and g_total >= a and s_total >= b:
            answer = min(mid, answer)
            end = mid - 1
        else:
            start = mid + 1
    
    return answer