문제 링크

잡담

레벨2 문제가 아닌 듯 했던 문제 ... 꽤 어려웠다.

반례 찾는 것이 어려웠는데 질문하기에서 반례를 얻어 왔다.

박종인님에게 감사를! 🙏

설계

0. 목표는 finish와 target을 같게 만드는 것이다.
   finish는 초기값 0이고 target은 모든 트럭 무게합이다.
   다시 말해, 모든 트럭이 다 통과할 때까지 아래 작업을 수행하겠다는 의미

1. 시간이 흐른다 (answer += 1)

2. 다리 길이가 다 찼으면 pop을 하여 finish에 더해준다.

3. 다리를 건널 수 있는지 확인하고 트럭을 append

4. 건널 수 없으면 0을 추가

4번을 상세히 설명하면 다리의 무게 제한 때문에 한 대의 트럭이 다리를 선점하고 있는 경우도 있다.

따라서, 이 트럭이 다 지나갈 때까지 기다려야 하는데 시간이 흐르는 만큼 다리가 차는 것을 구현하기 위하여 임의값 0을 넣어준 것.

예를 들어,

길이 5, 가능 무게 5, 트럭 무게 [2,2,2,2,1,1,1,1,1]

라고 했을 때

초반 다리는 [2,2,0,0,0]으로 될 것이다.

(왜냐하면 가능 무게가 5이기 때문에 [2,2,2,0,0]은 불가)

최종적으로 0번 조건을 만족할때까지 1~4번을 수행하면

answer가 최소 시간이 된다.

전체 코드

from collections import deque

def solution(bridge_length, weight, truck_weights):
    answer = 0
    finish = 0
    target = sum(truck_weights)
    truck_weights = deque(truck_weights)
    road = deque([])
    while finish != target:
        answer += 1
        if len(road) == bridge_length:
            finish += road.popleft()
            if not road[0]:
                while road and not road[0]:
                    road.popleft()
        if truck_weights and sum(road)+truck_weights[0] <= weight:
            road.append(truck_weights.popleft())
        else:
            road.append(0)
    return answer