트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다. 예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.
따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다. solution 함수의 매개변수로 다리에 올라갈 수 있는 트럭 수 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭 별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.
제한 조건
bridge_length는 1 이상 10,000 이하입니다.
weight는 1 이상 10,000 이하입니다.
truck_weights의 길이는 1 이상 10,000 이하입니다.
모든 트럭의 무게는 1 이상 weight 이하입니다.
3. 접근 기준
이 문제는 “현재 다리 위 상태”를 계속 업데이트하는 구조다. 따라서 다음 기준으로 접근해야 한다.
시간은 1초씩 흐른다.
매 초마다:
다리 위 트럭을 한 칸 이동
조건을 만족하면 새로운 트럭 진입
끝에 도달한 트럭은 제거
즉, 시간 단위 시뮬레이션 문제다.
4. 사용한 패턴 / 알고리즘
큐(Queue)
대기 트럭 큐 → 아직 다리에 올라가지 않은 트럭
다리 큐 → 현재 다리 위 상태를 표현 → 길이를 bridge_length로 고정
다리 큐는 단순 큐가 아니라 “현재 다리 상태를 그대로 표현하는 배열”이라고 보면 이해가 쉽다.
5. 핵심 아이디어
다리 큐를 항상 고정 길이로 유지한다.
매 초마다:
popleft() → 한 칸 이동
새로운 값 append() → 진입 or 빈 공간(0)
여기서 중요한 점은:
트럭이 못 올라가면 0을 넣는다 → 시간은 흐르지만 아무도 못 올라간 상황을 표현
6. 풀이 코드
from collections import deque
def solution(bridge_length, weight, truck_weights):
time = 0
bridge = deque([0] * bridge_length)
trucks = deque(truck_weights)
current_weight = 0
while bridge:
time += 1
# 1. 한 칸 이동 (앞에서 빠짐)
current_weight -= bridge.popleft()
# 2. 트럭 넣을 수 있는지 확인
if trucks:
if current_weight + trucks[0] <= weight:
t = trucks.popleft()
bridge.append(t)
current_weight += t
else:
bridge.append(0)
return time
7. 동작 흐름 예시
예:
bridge_length = 2
weight = 10
trucks = [7, 4, 5, 6]
흐름은 다음과 같다:
시간 1: [0, 7] 시간 2: [7, 0] 시간 3: [0, 4] 시간 4: [4, 5] ...
8. 핵심 로직 요약
이 문제의 핵심은 시간 흐름에 따라 다리 상태를 큐로 유지하면서 업데이트하는 것이다.
다리는 길이가 고정된 큐로 표현한다.
매 초마다 popleft()로 트럭을 한 칸 이동시킨다.
현재 다리 위 총 무게를 기준으로 새로운 트럭 진입 여부를 판단한다.
진입 가능하면 트럭을 넣고, 불가능하면 0을 넣어 시간을 유지한다.
모든 트럭이 빠져나갈 때까지 이 과정을 반복한다.
결국, “다리 상태를 큐로 유지 + 매 초 상태 갱신 + 조건 기반 진입 제어” 이 세 가지가 전체 로직의 핵심이다.
