백준 13335 [트럭] 파이썬

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

 

생각보다 시간이 오래 걸렸다. 

알고리즘은 간단한데.. 구현하는게 생각보다 어려웠다.

#백준 13335 트럭
from collections import deque
n,w,l=map(int,input().split()) # 트럭수, 통과시간, 제한하중
trucks=list(map(int,input().split())) #트럭 배열 저장
trucks=deque(trucks) # 트럭 배열 덱으로 변환
truck_on_brdg=deque([]) # 다리위에 있는 트럭 덱 초기화
ans=0 #정답 (총 시간간)
total_weight=0 # 총 무게 
def search():
    global ans
    global total_weight
    i=0
    while i<n: #모든 트럭이 통과하지 않았다면
        if total_weight+trucks[i]>l: #현재 다리위에 트럭이 있어 다음 트럭이 들어올 수 없을 때
            time_left=truck_on_brdg[0][1] #가장 앞에 있는 트럭의 남은 시간만큼 경과 시킴
            ans+=time_left
            total_weight-=truck_on_brdg[0][0] #가장 앞에 있는 트럭의 무게 만큼 총 무게에서 뺌
            truck_on_brdg.popleft() #가자 앞에 있는 트럭은 다리를 통과
            for j in range(len(truck_on_brdg)-1,-1,-1):  # 가장 앞에 있는 트럭이 다리를 통과하는데 걸리는 시간만큼 다리위의 나머지 트럭들의 남은 시간을 빼줌
                truck_on_brdg[j][1]-=time_left
            if total_weight+trucks[i]<=l: #만약 트럭이 통과하고 다음(새로운) 트럭이 들어올 수 있다면 추가
                truck_on_brdg.append([trucks[i],w])
                total_weight+=trucks[i]
                i+=1
                continue
        elif total_weight+trucks[i]<=l: #현재 다리에 다음 트럭이 들어올 수 있다면 추가
            if truck_on_brdg:
                for j in range(len(truck_on_brdg)-1,-1,-1):
                    truck_on_brdg[j][1]-=1
                if truck_on_brdg[0][1]==0:
                    total_weight-=truck_on_brdg[0][0]
                    truck_on_brdg.popleft()
            total_weight+=trucks[i]
            truck_on_brdg.append([trucks[i],w])
            ans+=1
            i+=1

search()
if truck_on_brdg: #혹시 다리위에 남은 트럭이 있다면 통과 시킴
    while truck_on_brdg:
        time_left=truck_on_brdg[0][1]
        ans+=time_left
        truck_on_brdg.popleft()
        for j in range(len(truck_on_brdg)-1,-1,-1):
            truck_on_brdg[j][1]-=time_left
print(ans)

갈길이 멀다.

 

깔끔하게 정리된 GPT의 코드를 첨부한다.

from collections import deque

def truck_on_bridge(n, w, l, trucks):
    bridge = deque([0] * w)  # 다리 길이만큼 0으로 채움
    truck_queue = deque(trucks)  # 트럭 대기열
    time = 0  # 경과 시간
    bridge_weight = 0  # 현재 다리 위 트럭 무게 합

    while bridge:  # 다리 위에 트럭이 남아있는 동안
        time += 1
        bridge_weight -= bridge.popleft()  # 다리에서 나가는 트럭 무게 제거

        if truck_queue:  # 대기 중인 트럭이 있다면
            if bridge_weight + truck_queue[0] <= l:  # 다리가 견딜 수 있는 무게 확인
                new_truck = truck_queue.popleft()  # 트럭 진입
                bridge.append(new_truck)
                bridge_weight += new_truck
            else:
                bridge.append(0)  # 다리 공간 유지 (빈 공간)

    return time

# 입력 예시
n, w, l = map(int, input().split())  # 트럭 수, 다리 길이, 최대 하중
trucks = list(map(int, input().split()))  # 트럭 무게 리스트

# 결과 출력
print(truck_on_bridge(n, w, l, trucks))

그냥 실제로 다리위에 트럭이 지나가는걸 시뮬레이션으로 구현하면 된다...