벡터 압축

시간 제한5초메모리 제한512 MB

요약

N차원 벡터 M개를 임의의 순서로 처리하되 각 벡터를 그대로 저장하거나 이전 벡터의 실수배를 뺀 잔차로 저장할 때, 저장된 벡터들의 제곱 길이 합의 최솟값을 구한다.

난이도: 어려움10점 중 8점
유형: 그리디, 기하, 수학, 동적 계획법
정답자: 아직 제출이 없습니다

문제

비밀 실험의 결과를 기록하려고 한다. 이 결과는 N차원 벡터의 큰 집합으로 이루어져 있다. 결과가 매우 커질 수 있으므로 압축을 고려하고 있다. 다행히 절댓값이 작은 벡터에 대한 좋은 압축 방법이 이미 있으므로, 벡터를 전처리해서 값이 작아지도록 만들면 된다.

벡터 집합은 임의의 순서로 기록할 수 있다. v1, v2, ..., vM 순서로 처리한다고 하자. 각 벡터 vi는 그대로 기록하거나 차분 벡터로 기록한다. 차분으로 기록할 때는 이미 선택된 벡터 vj(j<i)와 실수 r을 임의로 고를 수 있다. 그러면 실제로 기록되는 벡터 값은 (vi−rvj)이다. r과 j의 값은 압축률에 큰 영향을 주지 않으므로 신경 쓰지 않아도 된다.

벡터 집합이 주어졌을 때, 기록된 벡터들의 길이의 제곱 합의 최솟값을 계산하는 프로그램을 작성하시오.

입력

입력은 다음과 같은 형식이다.

N M
v1,1 v1,2 … v1,N
…
vM,1 vM,2 … vM,N

첫째 줄에는 두 정수 N과 M(1≤N,M≤100)이 주어진다. N은 각 벡터의 차원이고 M은 벡터의 개수이다. 다음 M개의 줄에는 각각 N개의 부동 소수점 값 vi,j(−1.0≤vi,j≤1.0)가 주어지며, 이는 i번째 벡터의 j번째 원소 값을 나타낸다.

출력

기록된 벡터들의 길이의 제곱 합의 최솟값을 출력한다. 출력의 절대 오차는 10−6을 넘지 않아야 한다.

예제3

예제 1
입력
```
2 3
1.0 1.0
-1.0 0.0
0.5 0.5
```
예상 출력
```
1.0
```
예제 2
입력
```
1 1
1.0
```
예상 출력
```
1.0
```

예제 3

입력

4 3
1.0 1.0 0.0 0.0
-1.0 0.0 -1.0 0.0
0.5 0.5 0.5 0.5

예상 출력

3.0