와이파이 설치

면접 대비

시간 제한1초메모리 제한128 MB

요약

수직선 위 소들의 위치를 모두 덮도록 기지국을 세우되, 길이 2r 구간을 덮는 기지국의 비용이 A + B*r일 때 총비용의 최솟값을 구한다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 정렬, 그리디, 수학
정답자: 아직 제출이 없습니다

문제

농부 존의 소 $N$ 마리 ( $1 \le N \le 2000$ )가 헛간에서 목초지로 이어지는 직선 경로 위 여러 위치에 서 있습니다. 이 경로는 하나의 1차원 수직선으로 생각할 수 있습니다. 소들은 서로 계속 연락하기를 원하므로, 존은 모든 소가 무선 신호를 받을 수 있도록 여러 위치에 와이파이 기지국을 설치하려고 합니다.

기지국의 가격은 신호를 전송할 수 있는 거리(출력)에 따라 달라집니다. 출력이 $r$ 인 기지국의 가격은 $A + B \cdot r$ 이며, 여기서 $A$ 는 기지국 설치의 고정 비용, $B$ 는 전송 거리 한 단위당 비용입니다. 위치 $x$ 에 이런 기지국을 설치하면 $x - r$ 부터 $x + r$ 까지의 범위에 있는 모든 소에게 신호를 전달할 수 있습니다. 출력이 $r = 0$ 인 기지국도 설치할 수 있지만, 이 경우 기지국과 정확히 같은 위치에 있는 소에게만 신호를 전달합니다.

$A$ 와 $B$ 의 값, 그리고 소들의 위치가 주어질 때, 모든 소에게 무선 신호를 제공하는 가장 저렴한 방법의 비용을 구하세요.

입력

첫째 줄: 공백으로 구분된 세 정수 $N$ , $A$ , $B$ ( $0 \le A, B \le 1000$ ).
다음 $N$ 개의 줄: 각 줄에는 소 한 마리의 위치를 나타내는 $0$ 이상 $1{,}000{,}000$ 이하의 정수가 하나씩 주어집니다.

출력

모든 소에게 무선 신호를 제공하는 최소 비용을 출력합니다.
답은 항상 $0.5$ 의 배수입니다. 답이 정수이면 소수점 부분 없이 출력하고, 그렇지 않으면 값 뒤에 .5를 붙여 출력합니다 (예: 57.5).

힌트

예를 들어 소 3마리가 위치 $7$ , $0$ , $100$ 에 있고, 출력이 $r$ 인 기지국의 가격이 $20 + 5r$ 이라고 합시다. 최적해는 위치 $3.5$ 에 출력 $3.5$ 인 기지국을 설치해 위치 $0$ 과 $7$ 의 소를 신호 범위에 넣고, 위치 $100$ 에 출력 $0$ 인 기지국을 하나 더 설치하는 것입니다. 이때 총 비용은 $(20 + 5 \cdot 3.5) + (20 + 5 \cdot 0) = 37.5 + 20 = 57.5$ 입니다.

예제4

예제 1
입력
```
3 20 5
7
0
100
```
예상 출력
```
57.5
```
예제 2
입력
```
1 10 5
42
```
예상 출력
```
10
```
예제 3
입력
```
2 20 5
0
100
```
예상 출력
```
40
```
예제 4
입력
```
2 1 1
0
1
```
예상 출력
```
1.5
```