문제

BOJ 13335: 트럭 https://www.acmicpc.net/problem/13335

풀이

조건

• 트럭의 순서는 바꿀 수 없다.
• 다리의 길이는 w 단위길이(unit distance)이며, 각 트럭들은 하나의 단위시간(unit time)에 하나의 단위길이만큼만 이동할 수 있다고 가정한다.
• 다리 위에는 단지 w 대의 트럭만 동시에 올라갈 수 있다.
• 동시에 다리 위에 올라가 있는 트럭들의 무게의 합은 다리의 최대하중인 L보다 작거나 같아야 한다.
• 다리를 건너는 최단시간을 구한다.

풀이 순서

• 다리의 상태와 트럭의 상태를 deque으로 구현한다.

• 다리에 빈 공간(0)을 다리 길이만큼(w) 추가해놓음

• 다음에 출발할 트럭의 무게를 미리 구해놓고 다리에 추가할 수 있는지 무게를 비교한다.

• while문을 돌 때 마다 result를 +1 해준다.(시간이 계속 흐른다고 생각)

• 조건에 맞춰 cars에서 트럭 하나를 빼고 bridge에 추가해주며 정답을 구한다.

• 아래 주석을 보면서 이해하는 것이 더 쉽다.

코드

Python

import sys
from collections import deque

n, w, L = map(int, sys.stdin.readline().split())

# 트럭들
cars = deque(map(int, sys.stdin.readline().split()))

# 다리 상태
bridge = deque()
# 다리에 빈 공간 넣어주기
for _ in range(w):
    bridge.append(0)

result = 0
while True:
    # 모든 트럭이 출발했고 다리 위에 트럭이 없다면 종료
    if len(cars) == 0 and sum(bridge) == 0:
        break
    
    # 기다리는 트럭들 중 가장 앞에 있는 트럭의 무게를 저장함
    if len(cars) > 0: # 출발하지 않은 자동차가 남아 있다면
        last_car = cars[0]
    else: # 남은 트럭이 없으면 빈 공간(0)을 넣어줌
        last_car = 0

    bridge.popleft() # 다리에서 빈 공간 하나 빠짐
    total_weight = sum(bridge) # 현재 다리에 있는 총 무게 구함

    # 출발해야 하는 트럭의 무게와 현재 다리에 있는 트럭의 무게를 더해 비교
    if total_weight + last_car > L:
        # 트럭이 다리에 추가될 수 없다면
        # 시간(result)은 +1
        # 다리에 빈 공간(0) 추가
        result += 1
        bridge.append(0)
    else:
        # 트럭이 다리에 추가될 수 있다면
        # 시간(result)은 +1
        result += 1
        # 트럭이 남아 있다면 하나 제거해줌
        # 이 부분은 위에서 출발할 트럭의 무게를 미리 구해놨기 때문에 pop()만 해줘도 됨
        if len(cars) > 0:
            cars.popleft()
        # 다리에 출발할 트럭 추가
        bridge.append(last_car)

print(result)

정리

• 처음에 문제를 제대로 이해하지 못해 한 번 올라간 트럭이 모두 내려간 뒤에 다음 트럭들이 출발할 수 있는 것으로 착각해서 틀렸었다.