[BOJ] 13335. 트럭(Python) / Simulation

13335번: 트럭

문제 설명다리의 길이와 다리의 최대하중, 그리고 다리를 건너려는 트럭들의 무게가 순서대로 주어졌을 때, 모든 트럭이 다리를 건너는 최단시간을 구하는 프로그램을 작성하라.

# 21분 소요

• 사용 알고리즘 : 문제에서 주어진 그대로 구현하는 Simulation 문제
• 전체적인 흐름은 아래 코드에 주석으로 달아놓았고,
• solve() 함수에서 중요! 표시한 부분을 보면,
  • trucks에서 맨 앞의 트럭이 다리로 이동할 수 있는 조건은
  • 현재 다리의 길이가 W보다 작고 and (맨 앞 트럭의 무게 + 현재 다리에 있는 트럭들의 무게) 가 다리의 최대 하중 L보다 작거나 같으면 이동할 수 있다!
  • 대기하는 trucks가 없어지는 순간 while문을 탈출한 것이므로 다리 위의 트럭까지 무사 이동시켜야 끝난다.
  • 그래서 time(대기 트럭 없을 때까지의 시간) + W(다리의 길이)를 리턴한다!

 

파이썬 코드는 다음과 같다.

---

from sys import stdin
input = stdin.readline
from collections import deque

def solve():
    time = 0
    bridge = deque([0] * W)		# 현재 다리 상태 표현
    while trucks:
        bridge.popleft()		# 다리에서 단위 길이만큼 이동
        x = trucks[0]			# trucks의 첫번째 트럭 무게
        if len(bridge) < W and sum(bridge) + x <= L:	# 중요!
            bridge.append(trucks.popleft())
        else:
            bridge.append(0)	# pop하지 못했다면 단위 길이만큼 이동 표현
        time += 1
    # trucks에 요소가 없어지는 순간 반복문 끝나므로 다리의 길이만큼 time에 추가
    return time + W

# n : 다리를 건너는 트럭의 수, w : 다리의 길이, L : 다리의 최대하중
N, W, L = map(int, input().split())
trucks = deque(map(int, input().split()))

print(solve())

---

• 시간 : 156ms / 메모리 : 125800kb
• 고찰 : 예전에 프로그래머스에서 완전 비슷한 문제 풀었던 기억이 있어서 금방 풀어냈다. 간단한 시뮬레이션 문제였다!