[알고리즘] 백준 파이썬 13335 트럭

다리 길이 w만큼 트럭이 동시에 올라갈 수 있고, 다리의 최대하중 L을 초과해서는 안 된다.
트럭들은 1단위 시간에 1단위 거리씩만 전진할 수 있으며, 다리 위에 완전히 올라가지 못한 트럭의 무게는 아직 다리에 가해지는 무게로 계산하지 않는다는 점이 핵심이다.

예시로, 다리 길이 w=2, 최대하중 L=10, 트럭 무게가 [7,4,5,6]일 때, 모든 트럭이 다리를 건너는 최단 시간은 8이 된다.

---

문제 조건 및 분석

1. 트럭의 수 n: 1≤n≤1,000
2. 다리의 길이 www: 1≤w≤100
3. 최대하중 LLL: 10≤L≤1,000
4. 트럭 무게: 각 트럭의 무게 ai​는 1≤ai≤10

이때, 모든 트럭이 다리를 건너는 최단 시간을 구해야 한다.

---

입력 범위

• n이 최대 1,000이므로, 각 트럭을 순차적으로 확인하면서 시간을 계산해도 충분히 빠르게 동작한다.
• 다리 길이 w 최대 100, 트럭 무게 합이 최대하중 L 이하가 되어야 함을 체크해야 한다.

---

시간 복잡도

• 매 시간 단위마다 트럭 진입 가능 여부, 진입 시 무게 합 체크, 그리고 이미 다리 위의 트럭 이동 처리 등이 필요하다.
• 최대 n개의 트럭이 전부 건너려면, 각 트럭마다 최소 w 이상의 시간이 걸린다.
• 알고리즘은 매 시간 단위마다 상태를 업데이트하므로, 최악의 경우 O(n×w)정도의 처리가 필요하다. n과 w가 크지 않으므로 충분히 계산 가능하다.

---

알고리즘 아이디어

1. 큐(Queue)를 이용한 구현
   • 다리 위에 있는 트럭의 위치나 무게를 큐로 관리한다.
   • 다리 길이 w만큼의 공간을 표현할 수 있도록, 큐의 길이를 최대 w로 유지한다.
   • 시간을 1씩 증가시키면서, 큐에서 맨 앞 요소(다리 맨 앞 트럭)가 다리를 완전히 빠져나갈 시점이 되면 큐에서 제거한다.
   • 새 트럭을 진입시킬 수 있는지(무게 합이 L 이하인지) 확인 후, 가능하다면 큐에 넣는다.
2. 트럭이 모두 건너는 시점 계산
   • 트럭이 모두 다리를 건너면 종료.
   • 시간을 카운팅하면서 진행한다.

---

코드 설계

1. 입력 받기
   • n,w,L
   • 트럭 무게 리스트
2. 변수 초기화
   • 현재 시간(time)
   • 다리 위 트럭 큐(길이를 최대 w로 유지)
   • 현재 다리에 올라간 트럭들의 무게 합
3. 반복
   • 시간 1 증가
   • 큐에서 맨 앞 트럭이 w칸을 모두 이동했으면 큐에서 제거
   • 새 트럭을 올릴 수 있는지 무게 합 확인 후, 올릴 수 있으면 큐에 삽입
   • 모든 트럭이 통과했는지 체크
4. 출력
   • 마지막에 증가된 시간

---

시도 회차 및 수정 사항

1. 초기 구현
   • 큐에 (트럭무게, 현재 위치)와 같은 정보를 담고 매 시간마다 위치를 +1씩 업데이트.
   • 위치가 w가 되면 큐에서 제거.
2. 최대하중 체크
   • 큐에 있는 트럭 무게 합을 구해 L과 비교 후, 초과하지 않으면 진입.
   • 트럭이 진입할 때는 항상 위치 0에서 시작.
3. 모든 트럭을 처리한 뒤
   • 현재 큐에 있는 트럭들도 전부 빠져나갈 때까지 시간 누적.

def solve():
    import sys
    input = sys.stdin.readline
    
    n, w, L = map(int, input().split())
    trucks = list(map(int, input().split()))
    
    # 다리를 나타낼 리스트(길이 w, 처음엔 모두 0)
    bridge = [0] * w
    
    sum_weight = 0  # 현재 다리 위 트럭 무게 합
    time = 0        # 흐른 시간
    index = 0       # 다음에 올라올 트럭의 인덱스
    
    while True:
        # 맨 앞(왼쪽) 트럭이 다리를 빠져나감
        out = bridge.pop(0)
        sum_weight -= out
        
        # 새로운 트럭 진입 가능 여부 확인
        if index < n:
            if sum_weight + trucks[index] <= L:
                # 트럭 진입
                bridge.append(trucks[index])
                sum_weight += trucks[index]
                index += 1
            else:
                # 무게를 버틸 수 없으면 0(빈 자리) 추가
                bridge.append(0)
        else:
            # 남아있는 트럭이 없다면 0 추가
            bridge.append(0)
        
        time += 1
        
        # 만약 다리 위 무게가 0이면 모든 트럭이 빠져나간 것
        if sum_weight == 0:
            break
    
    print(time)