[백준 08980] 택배 [Python]

문제

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

 

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

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

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

입력

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

출력

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

---

풀이

각 마을에서 보내는 박스들에 대해 최대한 많은 박스를 보내는 Greedy 문제다.

최적해에 대해 2중으로 생각해볼 수 있는 교육적인 문제였다.

우선, 동일한 출발지에 대해 도착지가 빠른 박스를 싣는 것이 최적의 해임이 자명하다.

출발지, 도착지 별로 정렬해주자. 

 

각 도착지에 배송 예정인 박스들의 용량을 기록해줄 배열( hold )을 선언하자.

마을을 순서대로 지나가며, 최대 용량( C ) 이하라면 전부 배송을 해주자.

위에서 언급했듯, 현 순간의 최적해가 다음 차례에 대해서도 최적인지 고민해봐야 한다.

다음 마을에 도착했을 때, 도착한 마을이 도착지가 아닌 박스들에 대해 최적인지 다시 계산해야 한다.

도착한 마을에서 새로 실을 수 있는 박스들의 도착지와 비교하여 배송중인 박스를 배송하지 않고(처음부터 싣지 않고) 도착지가 더 빠른 새로운 박스를 싣는 경우를 생각해야 한다.

 

기존에 보유중인 박스와 비교해 최대 용량보다 얼마나 넘치는지 계산하고

도착지가 먼 순서대로 탐색을 진행한다.

탐색을 진행하며 도착지가 먼 박스들부터 제거해주자.

위 탐색이 끝난 후 탐색 결과를 hold와 현재 보유중인 용량( capacity )를 갱신해주자.

---

소스코드

보기

---

출처

8980번: 택배