[파이썬/Python] 백준 13335번: 트럭

📌 문제 : 백준 13335번

---

📌 문제 탐색하기

n : 트럭 수 $(1 ≤ n ≤ 1,000)$
w : 다리 길이 $(1 ≤ w ≤ 100)$
L : 다리 최대 하중 $(10 ≤ L ≤ 1,000)$
a: 각 트럭의 무게 $(1 ≤ a ≤ 10)$

여러 가지 조건을 만족하면서 모든 트럭이 다리를 건너는 최단 시간을 구하는 문제이다.

문제 풀이

⭐️ 다리 건너는 조건

• 다리 위엔 w 대 트럭만 동시에 올라갈 수 있다
  • 다리 길이 = w
  • 1 단위시간 = 1 단위길이 이동
• 동시에 올라간 트럭 무게의 합 ≤ L 만족해야 한다.

먼저 동시에 다리에 올라갈 수 있는 조건이 따로 존재하기 때문에 다리에 올라온 트럭 정보를 저장할 리스트를 정의한다.
→ 리스트는 다리 길이만큼 정의한다.

다리 리스트의 맨 앞을 pop하면서 입력 받은 순서대로 트럭의 무게를 리스트 맨 뒤부터 append해준다.

🚨 다리의 최대 하중 조건을 지켜야 한다.
→ 단계를 하나씩 진행할 때마다 다리 리스트에 저장된 무게 총합을 확인해준다❗️

위의 과정들을 진행할 때마다 시간을 의미하는 변수를 증가시켜서 최종 출력을 구하면 될 것이다.

가능한 시간복잡도

하중 계산 → $O(w)$
다리, 트럭 리스트 빌 때까지 반복 → $O(n + w)$

최종 시간복잡도
$O(w * (n + w))$로 최악의 경우 $O(100 * 1100) = O(110000)$으로 1초 내에 연산 가능하다.

알고리즘 선택

반복문으로 다리 리스트와 트럭 리스트가 모두 빌 때까지 반복 수행

---

📌 코드 설계하기

1. 필요한 입력 받기
2. 다리 리스트 정의
3. 시간 변수 정의
4. 다리 리스트에 아무것도 없을 때까지 반복 수행
   4-1. 시간 카운트
   4-2. 트럭 들어올 자리 비우기
   4-3. 트럭 다 지나갈 때까지 최대 하중 조건 지켜서 트럭 지나가기
5. 결과 출력
   
   

---

📌 시도 회차 수정 사항

1회차

• 다리에 트럭을 올릴 수 없을 때, 다리 리스트에 있는 정보를 하나 빼야한다고 생각해서 on_bridge.pop(0)을 했다.
• 생각해보니 반복 과정의 처음에서 pop을 해서 트럭이 들어올 빈 공간을 만들어줬는데 들어오지 못하니 다시 append(0)로 빈 공간을 채워줘야 했다.

---

📌 정답 코드

import sys

input = sys.stdin.readline

# n, w, L 입력
n, w, L = map(int, input().split())

# 트럭 무게 입력
trucks = list(map(int, input().split()))

# 다리 리스트 초기화
bridge = [0] * w

# 시간 계산 변수 정의
time = 0

# 트럭 올리는 과정 진행
while bridge:
    # 시간 증가
    time += 1
    # 빈자리 만들기
    bridge.pop(0)

    # 트럭 다 옮길 때까지 진행
    if trucks:
        if sum(bridge) + trucks[0] <= L:
            # 더해서 최대하중 안넘으면 트럭 추가
            bridge.append(trucks.pop(0))
        else:
            # 최대하중 넘으면 다리 위 제거
            bridge.append(0)

# 결과 출력
print(time)

• 결과