습격자 초라기

---

🔗 🔗 전체 1007번 문제

조건

---

문제

---

평면 상에 $N$개의 점이 찍혀있고, 그 점을 집합 $P$라고 하자. 집합 $P$의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 $P$의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, $P$에 속하는 모든 점은 한 번씩 쓰여야 한다.

$V$에 있는 벡터의 갯수는 $P$에 있는 점의 절반이다.

평면 상의 점이 주어졌을 때, 집합 $P$의 벡터 매칭에 있는 벡터의 합의 길이의 최솟값을 출력하는 프로그램을 작성하시오.

입력

---

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 다음과 같이 구성되어있다.

테스트 케이스의 첫째 줄에 점의 갯수 $N$이 주어진다. $N$은 짝수이다. 둘째 줄부터 $N$개의 줄에 점의 좌표가 주어진다. $N$은 20보다 작거나 같은 자연수이고, 좌표는 절댓값이 100,000보다 작거나 같은 정수다. 모든 점은 서로 다르다.

출력

---

각 테스트 케이스마다 정답을 출력한다. 절대/상대 오차는 $10^{-6}$까지 허용한다.

케이스

---

예제 1

---

• 입력

TC
1
2
3
4
5
6
7
8
9
2
4
5 5
5 -5
-5 5
-5 -5
2
-100000 -100000
100000 100000

• 출력

TC
1
2
0.000000000000
282842.712474619038

풀이

---

두 개의 점으로 하나의 벡터를 만들 수 있다. $N <= 20$이므로 주어지는 점의 최대 갯수는 20개다. $N = 20$이라고 가정하면, 만들 수 있는 벡터의 수는 그 절반인 10개다. 20개의 점을 어떻게 잇느냐에 따라서 벡터 10개를 만드는 수 많은 경우의 수가 발생한다. 이 경우의 수에서 벡터의 총합이 가장 작은 값을 계산하는 게 이 알고리즘의 결과다.(10개의 벡터 중 가장 짧은 벡터를 계산하는 것이 아님에 유의하자.)

이 알고리즘의 핵심은 $N$개의 원소에서 $N / 2$개의 벡터를 만들 수 있는 경우를 계산해서 최소값을 계산하면 된다. $N$의 최대값이 20으로 매우 작으므로 하나하나 비교하는 것이 가능하다. 애초에 알고리즘 자체가 Brute Force(무차별 대입 공격)으로 분류돼있기도 하고.

좌표 $(x_1, y_1), (x_2, y_2), (x_3, y_3), (x_4, y_4)$가 있으며, 이 좌표에서 두 벡터인 $v_1$, $v_2$를 만든다고 가정하자.(조건은 알고리즘 문제와 동일) $v_1$이 $(x_1, y_1), (x_2, y_2)$으로 이루어져 있으며, $v_2$는 $(x_3, y_3), (x_4, y_4)$로 이루어져있다고 가정하자. 각 벡터를 좌표를 통해 표현하면 아래와 같다.

$$v_1 = (x_2 - x_1, y_2 - y_1)$$ $$v_2 = (x_4 - x_3, y_4 - y_3)$$

벡터의 합은 벡터 좌표의 단순합으로 이루어진다.

즉, 벡터의 총합 $v$는 아래와 같이 표현할 수 있다.

$$v = v_1 + v_2 = (x_2 + x_4 - x_1 - x_3, y_2 + y_4 - y_1 - y_3)$$ $$||v|| = \sqrt{(x_2 + x_4 - x_1 - x_3)^2 + (y_2 + y_4 - y_1 - y_3)^2}$$

위 식으로 계산한 값의 최소값이 알고리즘의 해답이 된다. 즉, 우리는 $(x_1, y_1), (x_2, y_2), (x_3, y_3), (x_4, y_4)$을 조건에 맞게 조합해야한다. 각 조합의 $||v||$를 계산한 뒤, 이 중 최소값을 반환하면 될 것 같다.

무턱대고 10개의 벡터를 for문 돌려가며 하나하나 만드는 방법은 안 된다. 좀 더 효율적으로 벡터를 계산하는 방법을 생각해보자.

$v$식을 자세히 보면 쓸만한 특징일 하나 찾을 수 있는데, 각각의 좌표 $x$, $y$를 계산할 때 좌표의 절반은 더해지고, 절반은 빼진다. 좌표가 4개일 경우 2개는 더해지고, 나머지 2개는 빼진다. 만약 10개라면? 5개는 더해지고, 5개는 빼질 것이다.

이를 활용하면 전체 좌표 $N$의 절반인 $N / 2$만큼의 좌표 조합을 구한다면 어떨까? 반은 더해지는 좌표, 나머지 반은 빼지는 좌표로 구분할 수 있다. 이후 각 좌표를 더하고 빼주면 손쉽게 $||v||$를 계산할 수 있을 것이다.

따라서, 점을 반으로 나누어 양의 연산에 사용할 점과 음의 연산에 사용될 점의 경우의 수를 구하는 것이 이번 알고리즘의 핵심이다. $_nC_r$(조합, Combination)을 사용하면 이를 쉽게 구할 수 있을 겻이다. $_nC_{(n / 2)}$를 계산하여, 선택된 좌표는 더하고, 선택되지 않은 좌표는 뺀다.

예제 1의 $_4C_2$의 경우의 수는 아래와 같다.

위와 같은 이유로 예제 1에서 벡터 총합의 최소값은 0이 된다.

전체 소스

---

JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * 백준 전체 1007 문제 알고리즘 클래스
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/06/09/a1007">1007 풀이</a>
 * @since 2021.06.09 Tue 00:50:26
 */
public class Main
{
	// 결과
	private static double result;
	
	// 조합 선택 여부
	private static boolean[] isChecked;
	
	// 점의 배열
	private static int[][] P;
	
	/**
	 * 메인 함수
	 *
	 * @param args: [String[]] 매개변수
	 *
	 * @throws IOException 데이터 입출력 예외
	 */
	public static void main(String[] args) throws IOException
	{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		
		// 케이스 수
		int T = Integer.parseInt(reader.readLine());
		
		for (int i = 0; i < T; i++)
		{
			// 점의 갯수
			int N = Integer.parseInt(reader.readLine());
			
			result = Double.MAX_VALUE;
			
			isChecked = new boolean[N];
			
			P = new int[N][2];
			
			for (int j = 0; j < N; j++)
			{
				String[] temp = reader.readLine().split(" ");
				
				P[j][0] = Integer.parseInt(temp[0]);
				P[j][1] = Integer.parseInt(temp[1]);
			}
			
			combination(0, N / 2);
			
			System.out.println(result);
		}
		
		reader.close();
	}
	
	/**
	 * 조합 함수
	 *
	 * @param index: [int] 인덱스
	 * @param count: [int] 조합할 원소 갯수
	 */
	private static void combination(int index, int count)
	{
		// 조합할 원소 갯수가 더 이상 없을 경우
		if (count == 0)
		{
			result = Math.min(result, getVector());
		}
		
		// 조합할 원소 갯수가 아직 남아있을 경우
		else
		{
			for (int i = index; i < P.length; i++)
			{
				isChecked[i] = true;
				
				combination(i + 1, count - 1);
				
				isChecked[i] = false;
			}
		}
	}
	
	/**
	 * 벡터 계산 함수
	 *
	 * @return [double] 벡터 크기
	 */
	private static double getVector()
	{
		int x = 0;
		int y = 0;
		
		for (int i = 0; i < P.length; i++)
		{
			// 양수로 선택된 점일 경우
			if (isChecked[i])
			{
				x += P[i][0];
				y += P[i][1];
			}
			
			// 음수로 선택된 점일 경우
			else
			{
				x -= P[i][0];
				y -= P[i][1];
			}
		}
		
		return Math.sqrt(Math.pow(x, 2) + Math.pow(y, 2));
	}
}

분류

---

• 수학
• 브루트포스 알고리즘