월간챌린지 시즌 3

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

시간 1씩 증가시키며 금과 은을 운반했더니 시간초과가 나온다.

실패한 코드

def time_check(time, t, idx):
    if time % t == 0: 
        return idx
    return -1
            
def check_while(a, b, current_gold, current_silver):
    if a == 0 and b == 0:
        for i in current_gold:
            if i != 0:
                return (0)
        for i in current_silver:
            if i != 0:
                return (0)
        return (1)
    return (0)

def solution(a, b, g, s, w, t):
    current_gold = [0 for i in range(len(t))]
    current_silver = [0 for i in range(len(t))]
    return_flag = [0 for i in range(len(t))]
    answer = -1
    time = 0
    i = 0
    
    while (1):
        if check_while(a, b, current_gold, current_silver) == 1:
            break;
        for idx,tt in enumerate(t):
            i = time_check(time,tt,idx)
            if i >= 0 and return_flag[i] == 1:
                current_gold[i] = 0
                current_silver[i] = 0
                return_flag[i] = 0
            elif i >= 0 and return_flag[i] == 0:
                return_flag[i] = 1
                while a > current_gold[i] and g[i] > 0 and current_gold[i] + current_silver[i] < w[i]:
                    current_gold[i] += 1
                    g[i] -= 1
                while b > current_silver[i] and s[i] > 0 and current_silver[i] + current_gold[i] < w[i]:
                    current_silver[i] += 1
                    s[i] -= 1
                
                a -= current_gold[i]
                b -= current_silver[i]
        time += 1
    
    return (time -1)

2. 새로 작성한 코드

지나치게 반복문이 많이 돌아서 이분 탐색으로 방향을 틀어 코드를 다시 작성했다.

시간을 미리 정해놓고, 해당 시간 동안 최대로 퍼올 수 있는 광물의 양을 계산한다.
a, b로 주어진 조건에 만족을 하면 기존 answer와 값을 비교해 더 작은 값을 다시 answer의 값으로 설정한다.

위의 코드와 마찬가지로 광물을 부었을 때, 조건을 만족하면 자동차가 왕복하지않고 그 즉시 끝나기 때문에 미리 설정해 둔 시간 mid - time 에서 나눈 뒤 1 더해준다.

def solution(a, b, g, s, w, t):
    start = 0
    end = (10 ** 9) * (10 ** 5) * 4
    answer = (10 ** 9) * (10 ** 5) * 4

    while start <= end:
        mid = (start + end) // 2
        current_gold = 0
        current_silver = 0
        total = 0

        for i, time in enumerate(t):
            cnt = (mid - time) // (time * 2) + 1

            if cnt * w[i] > g[i]:
                current_gold += g[i]
            if cnt * w[i] <= g[i]:
                current_gold += cnt * w[i]
            if cnt * w[i] > s[i]:
                current_silver += s[i]
            if cnt * w[i] <= s[i]:
                current_silver += cnt * w[i]
            if s[i] + g[i] < cnt * w[i]:
                total += s[i] + g[i]
            if s[i] + g[i] >= cnt * w[i]:
                total += cnt * w[i]
        if current_gold >= a and current_silver >= b and total >= a + b:
            end = mid - 1
            answer = min(answer, mid)
        else:
            start = mid + 1

    return (answer)