728x90
문제를 간단히 설명하자면, 임의의 점이 N개 주어진다.
해당 N개의 점을 한 번씩 사용해서 만들 수 있는 벡터들의 합 중 최소값을 찾고, 길이를 구해야 한다.
우선 이 문제를 해결하기 위해 벡터의 성질을 알아야 했다.
점 (x0, y0)에서 점 (x1, y1)을 향하는 벡터: (x1 - x0, y1 - y0)
점 (x2, y2)에서 점 (x3, y3)을 향하는 벡터: (x3 - x2, y3 - y2)
벡터들의 합: (x1 + x3 - x0 - x2, y1 + y3 - y0 - y2)
해결 방법
1. N개의 점 중 N/2개의 좌표는 더하고 나머지 N/2개의 좌표는 빼면 된다.
2. 1번을 진행하며, 최소값을 찾는다.
우선 dfs를 통해 모든 경우의 수를 조회 후, 최소값을 찾아보기로 했다.
import java.util.Scanner;
public class Main {
static int totalX, totalY, target, vx, vy;
static int[][] arr;
static double min;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int i = 0; i < T; i++) {
int n = sc.nextInt();
target = n / 2; // 벡터 매칭에 사용될 값. 점의 절반 개수
arr = new int[n][2];
totalX = 0;
totalY = 0;
min = Double.POSITIVE_INFINITY;
// 좌표 입력 받기
for (int j = 0; j < n; j++) {
int x = sc.nextInt();
int y = sc.nextInt();
arr[j] = new int[]{x + x, y + y}; // 원래 좌표의 2배로 저장
totalX += x; // x 좌표의 총합
totalY += y; // y 좌표의 총합
}
// 시작 인덱스부터 target 이상인 경우에만 탐색 진행
for (int j = 0; arr.length - j >= target; j++) {
vx = totalX; // 벡터 x의 합 초기화
vy = totalY; // 벡터 y의 합 초기화
vectorCheck(j, 1); // 최소 벡터 합 계산
}
// 최소 벡터 합의 제곱근 출력
System.out.println(Math.sqrt(min));
}
}
// 최소 벡터 합 계산
private static void vectorCheck(int idx, int depth) {
vx -= arr[idx][0]; // x 좌표의 총합에서 해당 좌표의 2배만큼 뺌
vy -= arr[idx][1]; // y 좌표의 총합에서 해당 좌표의 2배만큼 뺌
if (depth >= target) { // target에 도달한 경우, 이전의 값과 비교하여 최소값 대입
min = Math.min((long) vx * vx + (long) vy * vy, min);
}
else { // 도달하지 못했다면, 다음 좌표 탐색
depth++;
for (int i = idx + 1; arr.length - i >= target - depth + 1; i++) {
vectorCheck(i, depth);
}
}
// 탐색 후 좌표 복원
vx += arr[idx][0];
vy += arr[idx][1];
}
}
벡터와 관련된 첫 문제라 많이 어려울거라 생각했지만, 벡터보다는 dfs를 구현하는데에 어려움을 겪었다.
dfs 문제를 좀 더 풀어봐야겠다.
'Algorithm' 카테고리의 다른 글
Algorithm - 백준 도키도키 간식드리미(자료구조, 스택) (0) | 2024.04.04 |
---|---|
Algorithm - 프로그래머스 여행경로(DFS) (0) | 2024.04.02 |
Algorithm - 프로그래머스 섬 연결하기(Greedy, Minimum Spanning Tree, Union Find) (0) | 2024.04.01 |
Algorithm - 백준 DNA 비밀번호(12891), 슬리이딩 윈도우 (0) | 2024.03.26 |
프로그래머스 : 양옆앞뒤 큰 수 찾기 (0) | 2023.06.22 |