택배 > 문제은행

본문 바로가기


알고리즘 다이나믹2

2063 : 택배

제한시간: 1000 ms    메모리제한: 0 MB
해결횟수: 55 회    시도횟수: 190 회   



KOI 택배 회사는 물품을 빠르고 정확하게 배송하기로 유명하다. 본점으로 수집된 물품은 각각 지정된 지점으로 배송되는데, 본점은 고속도로가 시작하는 곳에 있고, 지점들은 1번 부터 10,000번까지 번호 순서대로 고속도로를 따라 일정한 간격으로 놓여 있다.

 

75aaf69980fa1f33c5b54a688ed39a00_1450936 

물품을 옮기는 데는 트럭과 헬리콥터를 이용하는 두 가지 방법이 있다. 트럭은 본점에서 지점으로 또는 지점에서 다른 지점으로 물품을 옮기는 데 사용되고, 헬리콥터는 본점에서 지점으로 물품을 옮기는데 사용된다. 트럭이 한 물품을 운반하는데 비용은 그 물품의 운송 거리에 비례하고, 헬리콥터는 물품의 개수와 운송 거리와는 상관없이 비용이 일정하다. 트럭으로는 한 번에 하나의 물품을 운송할 수 있으나, 헬리콥터는 운송할 수 있는 물품의 개수는 제한이 없다. 항상 충분한 수의 트럭과 헬리콥터가 준비되어 있다고 가정한다.

 

예를 들어, 본점에 10번, 40번, 30번, 50번, 10번 지점으로 옮겨야 하는 5개의 물품이 접수되었는데, 물품 하나를 트럭으로 한 지점 간격 옮기는 데는 10만큼의 비용이 들고, 헬리콥터를 한 번 이용하는 데는 개수나 거리에 상과없이 200만큼의 비용이 든다고 하자.

 

5개의 물품을 모두 트럭을 이용해서 옮기면,

 

10x10 + 40x10 + 30x10 + 50x10 + 10x10 = 1400

 

으로 총 1400만큼의 비용이 든다.

 

하지만 10번 지점으로 가야하는 두 물품은 트럭으로 옮기고, 나머지 세 물품은 한꺼번에 40번 지점으로 헬리콥터를 이용해서 옮기면 40번 지점으로 갈 물품은 목적 지점에 도착되었고, 이어 30번 지점과 50번 지점으로 갈 물품을 40번 지점에서 각각 트럭을 이용하여 옮기면,

 

10x10 + 10x10 + 200 + 10x10 + 10x10 = 600

 

으로 총 600만큼의 비용이 든다.

 

배송할 물품의 총 개수와, 각 물품의 목적 지점, 트럭과 헬리콥터 사용 비용이 주어질 때, 모든 물품을 목적 지점으로 옮기는데 드는 총 비용의 최소값을 구하는 프로그램을 작성하시오.


입력의 첫째 줄에 배송해야 할 물품의 개수 N이 주어진다. N은 3,000이하의 자연수이다.
둘째 줄에는 각 물품의 목적 지점의 번호가 빈 칸을 사이에 두고 주어진다. 지점의 번호는 10,000이하의 자연수이다.
셋째 줄에는 물품 하나를 트럭으로 한 지점 간격 옮기는 데 드는 비용과 헬리콥터를 한 번 이용하는데 드는 비용이 빈 칸을 사이에 두고 차례대로 주어진다. 이들 비용은 각각 1,000 이하의 자연수이다.


첫째 줄에 모든 물품을 목적 지점으로 옮기는데 드는 총 비용의 최소값을 출력한다.
모든 입력에 대하여 가능한 배송 방법의 총 비용은 10억 이하의 자연수이다.

[Copy]
5
10 40 30 50 10
10 200
[Copy]
600





HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.