데이터 분석

시간 제한3초메모리 제한1024 MB

요약

x축을 K개의 구간으로 나누고 각 구간마다 높이 하나를 골라 N개 점까지의 세로 거리 합을 최소로 만든다.

문제

데이터 과학자 앨리스는 데이터를 분석하는 일을 받았다. 각 데이터는 2차원 좌표 $(x, y)$ 로 구성된다.

데이터 분석은 $x$ 축에 평행한 $K$ 개의 선분을 2차원 상에서 찾는 과정이다. 구체적으로 아래의 값들을 결정해야한다.

각 선분의 끝을 나타내는 $x$ 좌표 $0=p\_0 < p\_1 < \cdots < p\_K = 50\ 000$ , $i$ 번째 선분의 양 끝은 $p\_{i-1}$ 과 $p\_i$ 이다. $1 \leq i \leq K$
각 선분의 $y$ 좌표 $m\_1, m\_2, \cdots, m\_K$

물론 $m\_1, m\_2, \cdots, m\_k$ 의 값들을 아무렇게나 결정하면 안 된다. 분석의 정확도를 높이기 위해서, 분석의 오차를 정의한 다음 오차가 최소가 되도록 값을 결정해 줄 것이다. 오차는 다음과 같이 정의한다.

데이터 $(x, y)$ 의 오차는, $p\_{i-1} \leq x < p\_i$ 를 만족하는 $i$ 에 대해서 $|y - m\_i|$ 으로 정의한다.
전체 데이터에 대한 오차는 각 데이터 $(x, y)$ 의 오차의 합이다.

앨리스는 데이터 분석의 오차가 최소가 되도록 $p\_0, \cdots, p\_k$ 와 $m\_1, \cdots, m\_k$ 를 결정하고자 한다. 각 값을 적절히 결정했을 때, 데이터 분석의 오차의 최솟값을 구하시오.

첫 번째 줄에 데이터의 개수 $N$ 과 찾아야하는 선분의 개수 $K$ 가 공백으로 구분되어 주어진다.

이후 $N$ 개의 줄에 각 데이터 $(x, y)$ 가 공백으로 구분되어 주어진다. 단, 모든 데이터의 $x$ 값은 다르다.

데이터 분석의 오차가 최소가 되도록 $p\_0,\cdots, p\_k$ 와 $m\_1,\cdots, m\_k$ 의 값을 적절히 결정했을 때, 데이터 분석의 오차를 출력한다. 절대/상대 오차는 $10^{-4}$ 까지 허용한다.