BOJ 1007. 벡터 매칭
랭크 : 골드2
문제 풀이
특이하게도 총 벡터를 구하는 거라, 절반은 그대로, 나머지 절반은 -를 곱해서 더해서 나온 좌표와 원점의 거리를 구하면 됩니다. 따라서 dfs로 절반의 점을 - 처리 해주는 코드를 구성하였습니다. 시간 복잡도가 2^N이라고는 하였지만 실제로는 조건이 걸려있어서 2^N보다는 2^(N/2)에 가까울 것 같습니다.
#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;
int N, T;
double ans;
vector<pair<double, double>> storage;
void dfs(double totalx, double totaly, int step, int changed) {
if (changed == N/2) {
ans = min(ans, sqrt(totalx * totalx + totaly * totaly));
return ;
}
if (step >= N) return ;
dfs(totalx, totaly, step + 1, changed);
dfs(totalx - 2 * storage[step].first, totaly - 2 * storage[step].second, step + 1, changed + 1);
}
int main() {
fastio;
cin >> T;
while (T--) {
cin >> N;
ans = 1000000000.0;
storage.clear();
double tmp1, tmp2;
double totalx = 0; double totaly = 0;
for (int i=0; i < N; i++) {
cin >> tmp1 >> tmp2;
totalx += tmp1; totaly += tmp2;
storage.emplace_back(tmp1, tmp2);
}
dfs(totalx, totaly, 0, 0);
cout.precision(20);
cout << ans << endl;
}
}알고리즘 |
시간복잡도 |
공간복잡도 |
|---|---|---|
| Bruteforce, DFS | $O(2^N)$ | $O(N)$ |
'알고리즘 > 백준' 카테고리의 다른 글
| BOJ 9527. 1의 개수 세기 (0) | 2022.07.07 |
|---|---|
| BOJ 2887. 행성 터널 (0) | 2022.07.07 |
| BOJ 2623. 음악프로그램 (0) | 2022.07.06 |
| BOJ 17387. 선분 교차2 (0) | 2022.07.06 |
| BOJ 2162. 선분 그룹 (0) | 2022.07.06 |