백준 13335번: 트럭

백준 13335번: 트럭

 

13335번: 트럭

덱(deque)을 활용하여 풀었다

• 트럭의 무게를 리스트에 저장한다
• 다리의 길이 w 길이를 가진 덱을 선언한다. 이 덱은 다리의 상황을 나타낸다
• 트럭의 무게를 저장한 리스트가 빌 때까지 while문을 돌린다 
  • 트럭의 무게를 저장한 리스트[0] + 덱의 요소들의 합 <= L(다리의 최대하중) 일 경우
    • 덱의 가장 왼쪽에 (트럭의 무게를 저장한 리스트[0]) 을 추가하고 무게를 저장한 리스트에서는 pop()한다
  • 트럭의 무게를 저장한 리스트[0] + 덱의 요소들의 합 > L(다리의 최대하중) 일 경우
    • 트럭이 다리에 진입을 못하는 상황이다. 이 경우에는 다리에 있는 트럭들만 한 칸씩 이동하므로 덱의 가장 왼쪽에 0을 추가한다
  • time을 1 증가하고 덱의 가장 오른쪽을 pop()한다
• 덱에 0만 남아 있을 경우에는 time을 출력하면 된다
• 덱에 0 이외에 다른 숫자가 있는 경우
  • 이는 다리(덱)에 트럭이 남아 있는 경우이다
  • 덱의 왼쪽에서부터 탐색하여 0이 아닌 숫자가 저장된 곳을 찾아야 한다. 0이 아닌 곳을 찾으면 time + w - (0이 아닌 곳의 인덱스)를 출력하면 된다

아래는 파이썬 코드이다

 

	import sys
	from collections import deque
	n, w, l = map(int, sys.stdin.readline().split())
	a = list(map(int, sys.stdin.readline().split()))
	time = 0
	road = deque(0 for _ in range(w))
	while a:
	time += 1
	road.pop()
	v = a[0]
	if v + sum(r) <= l:
	r.appendleft(v)
	a.pop(0)
	else:
	r.appendleft(0)
	if road.count(0) == w:
	print(time)
	else:
	tmp = w
	while road.popleft() == 0:
	tmp -= 1
	print(time + tmp)

view raw BOJ_13335.py hosted with ❤ by GitHub