[Swift Algorithm] 택배 BOJ #8980

문제 설명

아래 그림과 같이 직선 도로상에 왼쪽부터 오른쪽으로 1번부터 차례대로 번호가 붙여진 마을들이 있다. 마을에 있는 물건을 배송하기 위한 트럭 한 대가 있고, 트럭이 있는 본부는 1번 마을 왼쪽에 있다. 이 트럭은 본부에서 출발하여 1번 마을부터 마지막 마을까지 오른쪽으로 가면서 마을에 있는 물건을 배송한다.

각 마을은 배송할 물건들을 박스에 넣어 보내며, 본부에서는 박스를 보내는 마을번호, 박스를 받는 마을번호와 보낼 박스의 개수를 알고 있다. 박스들은 모두 크기가 같다. 트럭에 최대로 실을 수 있는 박스의 개수, 즉 트럭의 용량이 있다. 이 트럭 한대를 이용하여 다음의 조건을 모두 만족하면서 최대한 많은 박스들을 배송하려고 한다.

• 조건 1: 박스를 트럭에 실으면, 이 박스는 받는 마을에서만 내린다.
• 조건 2: 트럭은 지나온 마을로 되돌아가지 않는다.
• 조건 3: 박스들 중 일부만 배송할 수도 있다.

마을의 개수, 트럭의 용량, 박스 정보(보내는 마을번호, 받는 마을번호, 박스 개수)가 주어질 때, 트럭 한 대로 배송할 수 있는 최대 박스 수를 구하는 프로그램을 작성하시오. 단, 받는 마을번호는 보내는 마을번호보다 항상 크다.

예를 들어, 트럭 용량이 40이고 보내는 박스들이 다음 표와 같다고 하자.

보내는 마을	받는 마을	박스 개수
1	2	10
1	3	20
1	4	30
2	3	10
2	4	20
3	4	20

이들 박스에 대하여 다음과 같이 배송하는 방법을 고려해 보자.

(1) 1번 마을에 도착하면

• 다음과 같이 박스들을 트럭에 싣는다. (1번 마을에서 4번 마을로 보내는 박스는 30개 중 10개를 싣는다.)

보내는 마을	받는 마을	박스 개수
1	2	10
1	3	20
1	4	10

(2) 2번 마을에 도착하면

• 트럭에 실려진 박스들 중 받는 마을번호가 2인 박스 10개를 내려 배송한다. (이때 트럭에 남아있는 박스는 30개가 된다.)
• 그리고 다음과 같이 박스들을 싣는다. (이때 트럭에 실려 있는 박스는 40개가 된다.)

보내는 마을받는 마을박스 개수

보내는 마을	받는 마을	박스 개수
2	3	10

(3) 3번 마을에 도착하면 

• 트럭에 실려진 박스들 중 받는 마을번호가 3인 박스 30개를 내려 배송한다. (이때 트럭에 남아있는 박스는 10개가 된다.)
• 그리고 다음과 같이 박스들을 싣는다. (이때 트럭에 실려 있는 박스는 30개가 된다.)

보내는 마을	받는 마을	박스 개수
3	4	20

(4) 4번 마을에 도착하면 

• 받는 마을번호가 4인 박스 30개를 내려 배송한다

위와 같이 배송하면 배송한 전체 박스는 70개이다. 이는 배송할 수 있는 최대 박스 개수이다.

 

입력

입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이상 10,000이하 정수이다. 다음 M개의 각 줄에 박스를 보내는 마을번호, 박스를 받는 마을번호, 보내는 박스 개수(1이상 10,000이하 정수)를 나타내는 양의 정수가 빈칸을 사이에 두고 주어진다. 박스를 받는 마을번호는 보내는 마을번호보다 크다. 

 

출력

트럭 한 대로 배송할 수 있는 최대 박스 수를 한 줄에 출력한다.

 

입출력 예제

입력

6 60
5
1 2 30
2 5 70
5 6 60
3 4 40
1 6 40

출력

150

 

내 문제 풀이

import Foundation

let info = readLine()!.split(separator: " ").map({Int(String($0))!}) // [마을 개수, 트럭 용량]
let count = Int(readLine()!)!
var nums = [[Int]]() // [출발 마을, 도착 마을, 택배 개수]
var town = Array(repeating: 0, count: info[0]) // 마을 별 적재중인 택배 개수
var answer = 0

for _ in 0..<count { nums.append(readLine()!.split(separator: " ").map({Int(String($0))!})) }

nums.sort {
    if $0[1] != $1[1] { return $0[1] < $1[1] }
    else { return $0[0] < $1[0] }
}

for i in 0..<count {
    let max = (town[nums[i][0]-1..<nums[i][1]-1]).max()!
    if max < info[1] {
        let add = nums[i][2] + max > info[1] ? info[1] - max : nums[i][2]
        answer += add // 더해지는 택배 개수를 answer에 추가
        for j in nums[i][0]-1...nums[i][1]-2 {
            town[j] += add // 현재 택배가 지나가는 마을들에 add만큼의 택배 개수를 추가
        }
    }
}

print(answer)

👉 도착하는 마을 번호가 작은 택배부터 정렬해서 마을별로 트럭이 지날 때 적재된 양을 체크해주었다.

빨리 도착하는 마을을 기준으로 정렬하는 것이 이 문제의 핵심!

• 먼저 도착하는 시간을 기준으로 nums 배열을 정렬했고,
  도착 시간이 같을 경우 출발 시간 기준으로 정렬했다.
• for문은 위의 입출력 예제로 설명한 그림으로 첨부한다.
  

  

💡 피드백

• 어떻게 풀어야할지 고민하는데 시간이 좀 걸린 문제였지만,
  town 배열을 만들어주고 도착하는 시간을 기준으로 택배를 적재해주어야 하는 것을
  파악하니까 금방 풀 수 있었다.

 

---

 

문제

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