29893번 - 데이터 분석 서브태스크스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 1024 MB | 115 | 26 | 22 | 26.506% |
문제
데이터 과학자 앨리스는 데이터를 분석하는 일을 받았다. 각 데이터는 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}$까지 허용한다.
제한
- 주어지는 모든 수는 정수이다.
- $1\leq N \leq 3\,000$
- $1\leq K \leq \min(N, 10)$
- $0\leq x < 50\,000$
- $0\leq y \leq 1\,000$
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 30 | $N \leq 300$ |
| 2 | 70 | 추가 제약 조건이 없음. |
예제 입력 1
6 2 1 1 2 2 3 3 4 4 5 5 6 6
예제 출력 1
4.0000
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호