Problem Solving/boj
[BOJ] 13335. 트럭(Python) / Simulation
chesleashin
2021. 4. 21. 00:37
문제 설명다리의 길이와 다리의 최대하중, 그리고 다리를 건너려는 트럭들의 무게가 순서대로 주어졌을 때, 모든 트럭이 다리를 건너는 최단시간을 구하는 프로그램을 작성하라.
# 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
- 고찰 : 예전에 프로그래머스에서 완전 비슷한 문제 풀었던 기억이 있어서 금방 풀어냈다. 간단한 시뮬레이션 문제였다!