[백준 / BOJ] 8980 택배

문제

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

8980번: 택배

C만큼의 용량을 실을 수 있는 트럭이 있다.

N개의 마을이 있으며, A마을에서 B마을로 용량 D의 택배를 보낼려고한다.

M개의 보낼 택배의 시작장소, 도착장소 용량이 주어질때 트럭 한 대로 보낼 수 있는 최대한 많은 택배의 양을 구하는 문제다.

 

풀이

모든 경우를 봐줄경우, 구현에 따라 최악의 경우 2^M번 반복하므로 완전탐색으로는 시간안에 풀기 힘들다.

 

그리디를 이용해 풀은 문제다. 

 

문제를 잘 읽어보면 한가지 규칙을 알 수 있다.

- 마을 i에서 마을 i+1로 가는 택배가 있을경우 무조건 최대로 택배를 가져가는게 이득이다. 

이유는 다음과 같다.

 

1. 마을 i에서 마을 i+1로 가는 택배는 다음 택배를 담기위해서 i+1마을에 도착했을때 항상 배달이 완료되며, 그 만큼 트럭의 용량또한 다시 복구될것이기 때문이다.

 

2. 마을 i에서 마을 i+1로 가는 택배를 최대로 선택해서 마을 i에서 마을 i+a로 가는 다른 택배를 선택하지 못했더라도, 트럭 한 대가 한번에 담을수 있는 최대 용량이 있기때문에, 손해 볼 일이 없다.

(마을 i에서 마을 i+1로 가는 택배가 아닌, 마을 i에서 마을 i+a를 선택한다해서 같은 양을 배달할수는 있으나, 더 큰 양을 배달할수는 없음)

 

즉, 마을 i에서 마을 i+1로 가는 택배를 최대로 선택했을때 다른 택배를 배달하지 못해 얻을 손해는 없음을 알수있다.

 

이 때, 문제가되는것은, 마을 i에서 마을 i + a (a는 2 이상)으로 보내는 택배를 얼만큼 가져가야 하는가? 이다.

 

예 를 들어, 마을 1에서 마을 6로 가져가는 택배를 10만큼 선택했다고 하자. 그렇다면, 트럭의 적재용량은 마을 1에서 마을 6(배송완료) 까지 항상 10만큼 적은것이다.

즉, 마을 1에서 마을 6으로 가져가는 택배를 선택함으로써, 마을 2에서 마을 3으로 가는택배, 마을 2에서 마을 4로가는택배...등을 선택하지 못해 배달량이 줄어들수도있다.

따라서 마을 i에서 마을 i + a 로 가는 택배의 선택 여부는 (마을 2 -> 마을 3), (마을 2 -> 마을 4), (마을 2 -> 마을 5,) (마을 3 -> 마을 4) ... 등을 전부 봐 줘야한다. 

즉, 택배는 오래 들고있을수록 손해이므로, 목적지가 빠른 순서로 택배를 가져가는것이 항상 답임을 알수있다.

 

구현

1. 페어를 이용해서 벡터에 ((목적지,도착지),택배의 양) 순서로 저장하고 정렬한다.

 

2. 목적지가 빠른 순서로 택배를 얼만큼 담아야 하는지 찾는다. (항상 목적지는 출발지보다 뒤에 있기에 반례가 없다.)

2 - 1. 해당 출발지에서 택배를 얼만큼 담을 수 있는지 체크하는 배열 stor을 만들었다. stor[출발지] = 해당 출발지에서 담을 수 있는 택배의 양

2 - 2. 출발지에서 목적지까지 최대로 들고갈수있는 택배의 양을 검사한다. 예를들어, 출발지가 1이고 목적지가 6이라면, stor[1], stor[2], stor[3] ... stor[5]를 검사한다. (stor[6]에 도착하면 택배를 내려놓기 때문에 검사하지 않아도됨)

 

3. 출발지 부터 목적지까지 돌며, 담아야할 택배의 양을 stor배열에서 빼준다.

 

위 과정을 반복하면 답이 나옴.

 

시간복잡도는 매 탐색마다 N개의 마을을 반복하고, 총 M번 탐색하므로 O(NM)이다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/8980%20%ED%83%9D%EB%B0%B0/main.cpp

devxb/JJUNalgo