택배 배달과 수거하기
당신은 일렬로 나열된 n개의 집에 택배를 배달하려 합니다. 배달할 물건은 모두 크기가 같은 재활용 택배 상자에 담아 배달하며, 배달을 다니면서 빈 재활용 택배 상자들을 수거하려 합니다.
배달할 택배들은 모두 재활용 택배 상자에 담겨서 물류창고에 보관되어 있고, i번째 집은 물류창고에서 거리 i만큼 떨어져 있습니다. 또한 i번째 집은 j번째 집과 거리 j - i 만큼 떨어져 있습니다. (1 ≤
i ≤ j ≤ n)
트럭에는 재활용 택배 상자를 최대 cap개 실을 수 있습니다. 트럭은 배달할 재활용 택배 상자들을 실어 물류창고에서 출발해 각 집에 배달하면서, 빈 재활용 택배 상자들을 수거해 물류창고에 내립니다. 각 집마다 배달할 재활용 택배 상자의 개수와 수거할 빈 재활용 택배 상자의 개수를 알고 있을 때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 구하려 합니다.
각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거할 수 있습니다.
링크
문제에 대한 이해
- 일열로 나열된 n개의 집에 택배를 배달한다.
- 트럭에 실을 수 있는 택배상자의 개수는 최대 cap개이고, 각 집에 배달함과 동시에 빈 상자를 수거할 수 있다.
- 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 거리를 구한다.
접근 방법
어떤 방식으로 풀 수 있는가
우선 문제의 조건에서 총 배열의 길이가 10만까지 주어질 수 있다고 했으므로, 완전 탐색으로 해결은 불가능하다. 몇 번의 순회과정을 거쳐야 하는지도 알 수 없으며 그 과정에서 걸리는 시간 또한 예측이 불가능하기 때문이다.
그리디 방식으로 최적의 해를 구할 수 있는지 확인한다.
우선 문제의 접근 방식을 따른다. 문제에서는 택배를 수거할 때 물류센터에서부터 가장 먼 곳의 택배부터 배달을 시작했다(최대로 실을 수 있을 때까지의 인덱스에서부터 시작한다). 그렇기 때문에 뒤에서 부터 순회하면서 채울 수 있는 최대의 개수만큼 채우고, 빈 박스 역시 마찬가지의 방법으로 수거하면서 물류센터로 돌아가면 된다.
우선순위 큐로 접근하기
배열을 뒤에서부터 순회하면서 2번 순회하여 문제를 해결할 수 있을 수도 있지만, 이번 해결 방식에서는 우선순위 큐를 이용하였다.
- 우선순위 큐를 이용하여 가장 높은 인덱스부터 꺼내서 확인
- distance의 최댓값을 저장하기
- current_amount의 양 + 현재 인덱스의 값이 cap보다 작거나 같다면 값을 더하기
- 그렇지 않다면 순회를 멈추고 총 cap에서 뺀 값을 다시 우선순위 큐에 집어넣기
- 로직을 수거 시에도 적용하고, 저장한 최댓값에 * 2를 해서 total에 더하기
- 큐에 모든 요소가 없을 때까지 반복하기
주의해야 할 것
엣지 케이스를 고려해야 한다. 위 방식으로 로직을 작성했을 때 하나의 케이스에서 통과하지 못했다. 여기서 생각할 수 있는 엣지케이스는 모든 배열의 요소가 0인 경우인데, 해당 경우에서 total의 값이 0이 나와야 함에도 불구하고 그러지 않았다. 그 이유는 두 배열의 같은 인덱스의 값이 모두 0인 경우는 처음에 heap에 삽입할 때 넣지 않도록 처리해 주었다.