시간 초과의 늪에 빠져 결국 다른 분의 코드를 보았다.ㅠㅠ
처음에는 2개씩 짝을 짓는 dfs(재귀)로 풀어보고자 했다.
# 2개씩 N/2의 쌍을 만들어서 풀이.
import sys
input = sys.stdin.readline
T = int(input())
def add_vector(a, b):
return (a[0] + b[0], a[1] + b[1])
def make_vector(i, j):
dot_a, dot_b = dots[i], dots[j]
return (dot_b[0] - dot_a[0], dot_b[1] - dot_a[1])
def get_distance(v):
return (v[0]**2 + v[1]**2)**(1 / 2)
def dfs(is_selected, cur, cnt, v):
global N, min_sum_vector
# 모두 선택되었을 경우
if cnt == N:
min_sum_vector = min(min_sum_vector, get_distance(v))
return
i = is_selected.index(False, cur, N)
is_selected[i] = True
for j in range(i + 1, N):
if not is_selected[j]:
is_selected[j] = True
v_x, v_y = make_vector(i, j)
dfs(is_selected, i + 1, cnt + 2, add_vector(v, (v_x, v_y)))
dfs(is_selected, i + 1, cnt + 2, add_vector(v, (-v_x, -v_y)))
is_selected[j] = False
is_selected[i] = False
return
for _ in range(T):
N = int(input())
dots = [list(map(int, input().split())) for _ in range(N)]
min_sum_vector = int(1e9)
dfs([False] * N, 0, 0, (0, 0))
print(min_sum_vector)
그러나 시간 초과가 나서, N/2개의 숫자를 먼저 뽑는 방식으로 다시 풀어보았다. 또한 벡터의 합을 구하는 데, 몇가지 특징이 있어 그것도 함께 적용해 보았다.
참고 https://nerogarret.tistory.com/21
# 2개씩 N/2의 쌍을 만들어서 풀이.
import sys
from itertools import combinations
input = sys.stdin.readline
def distance(a):
return (a[0]**2 + a[1]**2)**(1 / 2)
T = int(input())
for _ in range(T):
N = int(input())
dots = []
total_sum_vector = [0, 0]
min_sum_vector = int(1e9)
# 모든 점 다 더하기
for _ in range(N):
a, b = map(int, input().split())
dots.append([a, b])
total_sum_vector[0] += a
total_sum_vector[1] += b
# 출발점 N/2 개 채택
for selected_dots in list(combinations(range(0, N), N // 2)):
start_sum_vector = [0, 0]
for dot in selected_dots:
start_sum_vector[0] += dots[dot][0]
start_sum_vector[1] += dots[dot][1]
cur_sum_vector = (total_sum_vector[0] - start_sum_vector[0] * 2,
total_sum_vector[1] - start_sum_vector[1] * 2)
min_sum_vector = min(min_sum_vector, distance(cur_sum_vector))
print(min_sum_vector)
그러나 이 코드도 시간 초과..ㅠㅠ 다른 분 코드랑 비교해보니, 다른 점은 숫자의 합을 구할때 나는 배열의 0번 인덱스, 1번 인덱스에 들어있는 수에 계속 더한다는 것이었고 다른 분은 그냥 2개의 변수에 따로 더한다는 점이 었다...
그 부분을 수정해서 적용하니.. 바로 통과..
# 2개씩 N/2의 쌍을 만들어서 풀이.
import sys
from itertools import combinations
input = sys.stdin.readline
def distance(a):
return (a[0]**2 + a[1]**2)**(1 / 2)
T = int(input())
for _ in range(T):
N = int(input())
dots = []
x_sum = 0
y_sum = 0
total_sum_vector = [0, 0]
min_sum_vector = int(1e9)
# 모든 점 다 더하기
for _ in range(N):
a, b = map(int, input().split())
dots.append([a, b])
x_sum += a
y_sum += b
# 출발점 N/2 개 채택
for selected_dots in list(combinations(dots, N // 2)):
start_x_sum = 0
start_y_sum = 0
for x, y in selected_dots:
start_x_sum += x
start_y_sum += y
cur_sum_vector = (x_sum - start_x_sum * 2,
y_sum - start_y_sum * 2)
min_sum_vector = min(min_sum_vector, distance(cur_sum_vector))
print(min_sum_vector)
다음부터는 고려해서 짜보아야겠다..!