[백준 13335] 트럭 (Swift)

문제 : 

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

13335번: 트럭

 

1. 문제 이해하기

• 강을 가로지르는 하나의 차선으로 된 다리가 하나가 있고, 이 다리를 n 개의 트럭이 건너가려고 합니다.
• 트럭의 순서는 바꿀 수 없으며, 트럭의 무게는 서로 같지 않을 수 있습니다.
• 다리 칸은 w이며, 다리 1칸 당 차 1대가 올라갈 수 있고, 다리 칸까지만 차가 올라갈 수 있습니다.
• 다리 위에 있는 차는 1초당 1칸씩 이동하며, 동시에 다리 위에 올라가 있는 트럭들의 무게의 합은 다리의 최대하중인 L보다 작거나 같아야 합니다.
• 모든 트럭이 다리를 건넜을 때의 시간을 리턴

 

2. 문제 풀이 생각하기

1. 처음에 문제를 글로 읽었을 때는 다리에 트럭이 한 번에 동시에 올라가는지, 트럭이 1초당 1칸씩 움직이는지에 대한 이해가 빠르게 되지 않았습니다.
2. while문과 Queue를 이용해서 while문 안에서 time을 증가시키고 큐에 값이 없을 때까지 큐에 넣고 빼고를 반복하면 된다고 생각했습니다. (큐를 사용한 이유는 트럭이 다리를 진입, 진출이 선입선출이기 때문입니다.)
3. 큐에는 [트럭 무게, 다리 진입 시간] 형태로 저장합니다.
4. 이 문제에서는 세 가지 상황을 생각해야 합니다. 트럭이 다리에 진입할 때, 트럭이 다리에서 진출할 때, 모든 트럭이 다리 위에 있을 때
5. 다리에 진입할 트럭이 남아 있는 경우 또는 다리 위에 트럭이 있는 경우 일 때만 while문을 실행합니다.
6. 만약 다리가 지탱할 수 있는 최대하중을 넘는 트럭이 나오면 index를 증가시키고 continue 합니다.
7. 시간 1 증가
8. 큐에 값이 있고, (첫 번째로 들어온 트럭의 시간 + 다리 길이) <= 현재시간 이라면 첫 번째 큐를 제거하고 해당 트럭의 하중을 sum에서 뺍니다.
9. 그리고 만약 건널 트럭이 남아 있고, (다리 위에 있는 트럭 하중 + 현재 트럭 하중) <= 다리가 지탱할 수 있는 하중 이라면 큐에 해당 트럭 데이터를 추가합니다.
10. 만약 남아 있는 트럭이 없고, 다리 위에 트럭이 없다면 종료
11. 5 ~ 10 반복

 

문제에서 그림 예시로 설명하겠습니다.

4 2 10
7 4 5 6

while문에서 다리에서 나가는 트럭을 먼저 확인한 후에 다리에 진입할 트럭을 확인해야 합니다.

 

3. 차근차근 구현하기

import Foundation

let data = readLine()!.components(separatedBy: " ").map { Int(String($0))! }
let (n, w, l) = (data[0], data[1], data[2])
let arr = readLine()!.components(separatedBy: " ").map { Int(String($0))! }
var q = [[Int]]() // 큐 -> [트럭 무게, 다리 진입 시간]
var index = 0 // 남아 있는 트럭 인덱스
var time = 0 // 시간
var sum = 0 // 다리 위에 있는 모든 트럭 무게

while index < arr.count || !q.isEmpty {
    // 다리가 지탱할 수 있는 최대하중보다 높은 무게의 트럭이 나왔을 때
    if index < arr.count && arr[index] > l {
        index += 1
        continue
    }

    time += 1

    // 다리 위에 있는 트럭이 다리를 지나감
    if !q.isEmpty && q[0][1] + w <= time {
        sum -= q.removeFirst()[0]
    }

    // 트럭이 다리 위로 진입
    if index < arr.count && sum + arr[index] <= l && q.count < w {
        q.append([arr[index], time])
        sum += arr[index]
        index += 1
    }
}

print(time)

 

4. 피드백

• 문제 이해 시간을 빠르게 가져갈 수 있도록 더 훈련해야겠다. 구현할 방법을 그림으로 표현하는 것을 연습하자.