주차장
면접 대비시간 제한15초메모리 제한512 MB
1번부터 M번까지의 주차 공간에 N명의 운전자를 서로 겹치지 않게 배정해 각자의 희망 위치까지 거리의 합을 최소로 만든다.
문제
M개의 주차 공간이 있는 주차장을 관리해야 한다. 주차 공간에는 1부터 M까지의 정수가 붙어 있다. 모든 주차 공간은 일렬로 놓여 있어, i번째 주차 공간은 (i – 1)번째와 (i + 1)번째 주차 공간을 이웃으로 갖는다. 다만 1번째 주차 공간은 2번째만, M번째 주차 공간은 (M – 1)번째만 이웃으로 갖는다.
처음에 모든 주차 공간은 비어 있다. 운전자가 N명 있고, 각자 선호하는 주차 공간이 하나씩 있다. i번째 운전자는 Ai번째 주차 공간에 주차하고 싶어 한다. i번째 운전자가 Bi번째 주차 공간에 주차하게 되면 불만족도를 |Ai - Bi|로 측정한다.
주차 공간의 수 M, 운전자의 수 N, 각 운전자가 선호하는 주차 공간 Ai가 주어질 때, 모든 운전자의 불만족도 합의 최솟값을 구하라.
입력
첫째 줄에 두 수 M과 N이 공백 하나를 사이에 두고 주어진다. 둘째 줄에 각 운전자가 선호하는 주차 공간 A1, A2, …, An이 주어진다.
출력
첫째 줄에 모든 운전자의 불만족도 합의 최솟값을 나타내는 수 하나를 출력한다.
제한
- 1 ≤ M ≤ 10,000
- 1 ≤ N ≤ 1,000
- N ≤ M
- 두 명 이상의 운전자가 같은 주차 공간을 사용할 수 없다.
- 모든 운전자의 불만족도 합은 각 운전자의 불만족도를 모두 더해 계산한다.
힌트
모든 운전자의 불만족도 합의 최솟값을 달성하는 한 가지 방법은 운전자들에게 다음과 같이 주차하도록 지시하는 것이다. B1 = 3, B2 = 5, B3 = 4. 각 운전자의 불만족도는 1, 0, 0이므로 불만족도 합은 1 + 0 + 0 = 1이다.