[백준] 트럭 [풀이 + 코드 + 어떤 논리 흐름을 가졌을까?]

구현

https://www.acmicpc.net/problem/13335

13335번: 트럭

 

코드

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

# n 트럭개수
# w 는 다리 길이
# l은 최대하중
n, w, l = map(int, input().split())

load, truck = deque([0] * w), deque(list(map(int, input().split())))

time = 0

while True:
	if len(truck) == 0 and load.count(0) == len(load):
		break
        
	# for i in range(1, len(load)):
	# 	load[i-1] = load[i]
	# 	load[i] = 0
    
	if load[-1] == 0:
		if truck and sum(load) + truck[0] <= l:
			load[-1] = truck.popleft()
		else:
			load.popleft()
			load.append(0)
			if truck and sum(load) + truck[0] <= l:
				load[-1] = truck.popleft()
	else:
		load.popleft()
		load.append(0)
		if truck and sum(load) + truck[0] <= l:
			load[-1] = truck.popleft()


	time += 1
print(time)

 

설명

 트럭 문제 같은 경우 특별히 아이디어를 가지고 구현을 하게 되는 문제 같다. 우선 이 문제 같은 경우 자꾸 논리가 꼬여서 구현하다가도 애매해서 다시 생각해 보게 되고 번복을 많이 했던 문제 같다. 우선 이 문제의 핵심은 크게 세 가지 정도로 볼 수 있을 것 같다.

 

 

앞 트럭이 지나가야 뒤에 트럭이 지나갈 수 있다.

 

다리 위에 올라올 수 있는 경우는 다리의 시작점이 비었을 때 그리고 올라오는 트럭의 무게와 다리에 있는

트럭들의 무게가 최대하중보다 작거나 같을 때

 

다리 위에 올라올 수 있다면 바로 올라와야 한다.

 

 

 크게 바라본다면 위 조건들을 가지고 생각해 볼 수 있다. 우선 그림 상에서도 정확히 표현해주고 있는데 앞 차가 지나가야 그다음 차가 지나가는 모습을 보여주고 있다. 또한 조건에서도 명시되어 있는데 다리 위에 올라가 있는 트럭들의 무게는 다리가 버틸 수 있는 최대 하중을 넘어서면 안 된다. 따라서 생각해 볼 수 있는 건 '트럭이 언제 다리 위에 올라갈 수 있는지' 그리고 최대 하중을 넘어서진 않으면서 최대한 다리 위에 많은 트럭들을 올리게 만드는 방법을 생각해야 한다. 우선 최대 하중을 넘어 서지는 않으면서 최대한 다리 위에 많이 놓이려면 최대 하중에 가까운 무게를 맞추면 된다. 최대 하중을 넘어서지만 않으면 되기 때문에 같아도 된다. 따라서 매초마다 앞 차가 이동함으로써 출발지에 빈 공간이 생기게 된다면 그때마다 최대 하중을 넘어서지만 않는다면 무조건 계속 올라오면 된다. 또한 트럭이 더 이상 없을 수도 있기 때문에 이 점도 고려해야 한다. 트럭이 없을 때는 끝나는 게 아니라 문제 목적상 '모든 트럭이 다리를 건너는'이라고 명시했기 때문에 모든 트럭들이 다 다리를 지나가야 된다는 걸 의미한다. 따라서 1개의 트럭만 있어 다리 위에 올라간다고 했을 때 이후 올라갈 트럭이 없다고 하더라도 모든 트럭이 다리를 다 지나가는 시간을 구해야 하기 때문에 1개의 트럭 또한 다리 위에 존재하며 그 다리 위를 다 지나갈 때 까지를 시간을 측정해야 한다는 뜻이 된다. 이러한 고려 사항들을 적절히 고려하여 구현하면 되는 문제지만 생각보다 아이디어를 찾는 시간이 오래 걸린 문제라고 생각한다.