[백준] 트럭 (13335번)

난이도 : Silver 1
Link : https://www.acmicpc.net/problem/13335
Tag : 구현, 자료구조, 시뮬레이션, 큐
풀이일자 : 2024년 9월 20일

📌 문제 탐색하기

N : 트럭의 개수
W : 다리의 길이
L : 다리 최대 하중

본 문제는 트럭의 무게가 순서대로 주어지고, 다리를 최단 시간으로 건널 수 있는 시간을 구하는 문제이다.

가능한 시간복잡도

다리의 길이와 트럭의 개수가 가능한 시간복잡도에 영향을 준다.
N은 1000이하 W는 100 이하 이므로 최악의 시간복잡도는 1000 * 100이므로 시간복잡도 상 문제는 없어 보인다.

📌 문제 접근 방법

deque를 이용하여 왼쪽방향과 오른쪽 방향에서 0과 트럭의 무게를 추가해주고 빼주면서 다리의 최대 하중을 넘지 않는지 확인하려고 한다.

경우의 수는 다음과 같다.

트럭이 다리 위에 올라 갈 수 있는 경우
- 차가 그저 추가되는 경우
- 차가 빠지고 차가 추가되는 경우
- 다리 위에 차가 지나갈때까지 기다리는 경우
- 추가되는 차는 없고 다리위에 차가 지나갈때 까지 기다리는 경우

다음과 같은 경우의 수들을 if문을 통해 걸리는 시간을 체크하려고 한다.

📌 코드 설계하기

1. n,w,l을 입력받는다.
2. car배열에 트럭의 무게를 저장한다.
3. bridge배열에 w길이만큼 0을 저장한다.
4. car_deque와 bridge_deque에 car와 bridge배열을 추가한다.
5. while문을 반복한다 (car_deque에 원소가 없거나 or birdge_deque에 모든 값이 0일때까지)
6. 앞서 말한 조건들을 추가한다.

      if len(car_deque) != 0:
           if sum(bridge_deque) + car_deque[0] <= l:
               bridge_deque.append(car_deque.popleft())
               bridge_deque.popleft()
               answer += 1
           else: #지나갈때 까지 차가 다리에 추가 못하는 경우
               bridge_deque.append(0)
               bridge_deque.popleft()
               answer += 1
               # 차가 빠져나가면서 차가 추가되는 경우
               if sum(bridge_deque) + car_deque[0] <= l and bridge_deque[-1] == 0:
                   bridge_deque[-1] = car_deque.popleft()
       else: #추가될 차는 없고 다리에 차가 있을경우
           bridge_deque.append(0)
           bridge_deque.popleft()
           answer += 1

7. answer를 출력한다.

📌 시도 회차 수정 사항

1. 틀렸습니다. (1%)
   조건을 잘못 맞췄다.

📌 정답 코드

from collections import deque
n,w,l = map(int,input().split()) # n: 자동차 개수 # w : 다리 길이  # l : 최대 하중
car = list(map(int,input().split()))
bridge = [0] * w
car_deque = deque(car)
bridge_deque = deque(bridge)

answer = 0

while car_deque or sum(bridge_deque) != 0:
    #다리 위에 올라 갈 수 있는 경우 (1.차가 추가 2.차가 빠지고)
    if len(car_deque) != 0:
        if sum(bridge_deque) + car_deque[0] <= l:
            bridge_deque.append(car_deque.popleft())
            bridge_deque.popleft()
            answer += 1
        else: #지나갈때 까지 차가 다리에 추가 못하는 경우
            bridge_deque.append(0)
            bridge_deque.popleft()
            answer += 1
            # 차가 빠져나가면서 차가 추가되는 경우
            if sum(bridge_deque) + car_deque[0] <= l and bridge_deque[-1] == 0:
                bridge_deque[-1] = car_deque.popleft()
    else: #추가될 차는 없고 다리에 차가 있을경우
        bridge_deque.append(0)
        bridge_deque.popleft()
        answer += 1
print(answer)