- [백준 / JAVA] 백준 알고리즘 1021번 회전하는 큐
- [백준 / JAVA] 백준 알고리즘 1020번 디지털 카운터
- [백준 / JAVA] 백준 알고리즘 1019번 책 페이지
- [백준 / JAVA] 백준 알고리즘 1018번 체스판 다시 칠하기
- [백준 / JAVA] 백준 알고리즘 1017번 소수 쌍
- [백준 / JAVA] 백준 알고리즘 1016번 제곱 ㄴㄴ수
- [백준 / JAVA] 백준 알고리즘 1015번 수열 정렬
- [백준 / JAVA] 백준 알고리즘 1014번 컨닝
- [백준 / JAVA] 백준 알고리즘 1013번 Contact
- [백준 / JAVA] 백준 알고리즘 1012번 유기농 배추
- [백준 / JAVA] 백준 알고리즘 1011번 Fly me to the Alpha Centauri
- [백준 / JAVA] 백준 알고리즘 1010번 다리 놓기
- [백준 / JAVA] 백준 알고리즘 1009번 분산처리
- [백준 / JAVA] 백준 알고리즘 1008번 A / B
👀 [백준 / JAVA] 백준 알고리즘 1007번 벡터
- [백준 / JAVA] 백준 알고리즘 1006번 습격자 초라기
- [백준 / JAVA] 백준 알고리즘 1005번 ACM Craft
- [백준 / JAVA] 백준 알고리즘 1004번 어린 왕자
- [백준 / JAVA] 백준 알고리즘 1003번 피보나치 함수
- [백준 / JAVA] 백준 알고리즘 1002번 터렛
- [백준 / JAVA] 백준 알고리즘 1001번 A - B
- [백준 / JAVA] 백준 알고리즘 1000번 A + B
- 백준 알고리즘 시작하기
습격자 초라기 🔗
조건 🔗
시간제한 | 메모리 제한 |
---|---|
2초 | 512MB |
문제 🔗
평면 상에 개의 점이 찍혀있고, 그 점을 집합 라고 하자. 집합 의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, 에 속하는 모든 점은 한 번씩 쓰여야 한다.
에 있는 벡터의 갯수는 에 있는 점의 절반이다.
평면 상의 점이 주어졌을 때, 집합 의 벡터 매칭에 있는 벡터의 합의 길이의 최솟값을 출력하는 프로그램을 작성하시오.
입력 🔗
첫째 줄에 테스트 케이스의 개수 가 주어진다. 각 테스트 케이스는 다음과 같이 구성되어있다.
테스트 케이스의 첫째 줄에 점의 갯수 이 주어진다. 은 짝수이다. 둘째 줄부터 개의 줄에 점의 좌표가 주어진다. 은 20보다 작거나 같은 자연수이고, 좌표는 절댓값이 100,000보다 작거나 같은 정수다. 모든 점은 서로 다르다.
출력 🔗
각 테스트 케이스마다 정답을 출력한다. 절대/상대 오차는 까지 허용한다.
케이스 🔗
예제 1 🔗
- 입력
TC
0 | 2 |
1 | 4 |
2 | 5 5 |
3 | 5 -5 |
4 | -5 5 |
5 | -5 -5 |
6 | 2 |
7 | -100000 -100000 |
8 | 100000 100000 |
- 출력
TC
0 | 0.000000000000 |
1 | 282842.712474619038 |
풀이 🔗
두 개의 점으로 하나의 벡터를 만들 수 있다. 이므로 주어지는 점의 최대 갯수는 20개다. 이라고 가정하면, 만들 수 있는 벡터의 수는 그 절반인 10개다. 20개의 점을 어떻게 잇느냐에 따라서 벡터 10개를 만드는 수 많은 경우의 수가 발생한다. 이 경우의 수에서 벡터의 총합이 가장 작은 값을 계산하는 게 이 알고리즘의 결과다.(10개의 벡터 중 가장 짧은 벡터를 계산하는 것이 아님에 유의하자.)
이 알고리즘의 핵심은 개의 원소에서 개의 벡터를 만들 수 있는 경우를 계산해서 최소값을 계산하면 된다. 의 최대값이 20으로 매우 작으므로 하나하나 비교하는 것이 가능하다. 애초에 알고리즘 자체가 Brute Force(무차별 대입 공격)으로 분류돼있기도 하고.
좌표 가 있으며, 이 좌표에서 두 벡터인 , 를 만든다고 가정하자.(조건은 알고리즘 문제와 동일) 이 으로 이루어져 있으며, 는 로 이루어져있다고 가정하자. 각 벡터를 좌표를 통해 표현하면 아래와 같다.
벡터의 합은 벡터 좌표의 단순합으로 이루어진다.
즉, 벡터의 총합 는 아래와 같이 표현할 수 있다.
위 식으로 계산한 값의 최소값이 알고리즘의 해답이 된다. 즉, 우리는 을 조건에 맞게 조합해야한다. 각 조합의 를 계산한 뒤, 이 중 최소값을 반환하면 될 것 같다.
무턱대고 10개의 벡터를 for문 돌려가며 하나하나 만드는 방법은 안 된다. 좀 더 효율적으로 벡터를 계산하는 방법을 생각해보자.
식을 자세히 보면 쓸만한 특징일 하나 찾을 수 있는데, 각각의 좌표 , 를 계산할 때 좌표의 절반은 더해지고, 절반은 빼진다. 좌표가 4개일 경우 2개는 더해지고, 나머지 2개는 빼진다. 만약 10개라면? 5개는 더해지고, 5개는 빼질 것이다.
이를 활용하면 전체 좌표 의 절반인 만큼의 좌표 조합을 구한다면 어떨까? 반은 더해지는 좌표, 나머지 반은 빼지는 좌표로 구분할 수 있다. 이후 각 좌표를 더하고 빼주면 손쉽게 를 계산할 수 있을 것이다.
따라서, 점을 반으로 나누어 양의 연산에 사용할 점과 음의 연산에 사용될 점의 경우의 수를 구하는 것이 이번 알고리즘의 핵심이다. (조합, Combination)을 사용하면 이를 쉽게 구할 수 있을 겻이다. 를 계산하여, 선택된 좌표는 더하고, 선택되지 않은 좌표는 뺀다.
예제 1의 의 경우의 수는 아래와 같다.
양의 좌표 | 음의 좌표 | ||
---|---|---|---|
(5, 5), (5, -5) | (-5, 5), (-5, -5) | (20, 0) | 20 |
(5, 5), (-5, 5) | (5, -5), (-5, -5) | (0, 20) | 20 |
(5, 5), (-5, -5) | (5, -5), (-5, 5) | (0, 0) | 0 |
(5, -5), (-5, 5) | (5, 5), (-5, -5) | (0, 0) | 0 |
(5, -5), (-5, -5) | (5, 5), (-5, 5) | (0, -20) | 20 |
(-5, 5), (-5, -5) | (5, 5), (5, -5) | (-20, 0) | 20 |
위와 같은 이유로 예제 1에서 벡터 총합의 최소값은 0이 된다.
전체 소스 🔗
JAVA
0 | import java.io.BufferedReader; |
1 | import java.io.IOException; |
2 | import java.io.InputStreamReader; |
3 | |
4 | /** |
5 | * 백준 전체 1007 문제 알고리즘 클래스 |
6 | * |
7 | * @author RWB |
8 | * @see <a href="https://blog.itcode.dev/posts/2021/06/09/a1007">1007 풀이</a> |
9 | * @since 2021.06.09 Tue 00:50:26 |
10 | */ |
11 | public class Main |
12 | { |
13 | // 결과 |
14 | private static double result; |
15 | |
16 | // 조합 선택 여부 |
17 | private static boolean[] isChecked; |
18 | |
19 | // 점의 배열 |
20 | private static int[][] P; |
21 | |
22 | /** |
23 | * 메인 함수 |
24 | * |
25 | * @param args: [String[]] 매개변수 |
26 | * |
27 | * @throws IOException 데이터 입출력 예외 |
28 | */ |
29 | public static void main(String[] args) throws IOException |
30 | { |
31 | BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); |
32 | |
33 | // 케이스 수 |
34 | int T = Integer.parseInt(reader.readLine()); |
35 | |
36 | for (int i = 0; i < T; i++) |
37 | { |
38 | // 점의 갯수 |
39 | int N = Integer.parseInt(reader.readLine()); |
40 | |
41 | result = Double.MAX_VALUE; |
42 | |
43 | isChecked = new boolean[N]; |
44 | |
45 | P = new int[N][2]; |
46 | |
47 | for (int j = 0; j < N; j++) |
48 | { |
49 | String[] temp = reader.readLine().split(" "); |
50 | |
51 | P[j][0] = Integer.parseInt(temp[0]); |
52 | P[j][1] = Integer.parseInt(temp[1]); |
53 | } |
54 | |
55 | combination(0, N / 2); |
56 | |
57 | System.out.println(result); |
58 | } |
59 | |
60 | reader.close(); |
61 | } |
62 | |
63 | /** |
64 | * 조합 함수 |
65 | * |
66 | * @param index: [int] 인덱스 |
67 | * @param count: [int] 조합할 원소 갯수 |
68 | */ |
69 | private static void combination(int index, int count) |
70 | { |
71 | // 조합할 원소 갯수가 더 이상 없을 경우 |
72 | if (count == 0) |
73 | { |
74 | result = Math.min(result, getVector()); |
75 | } |
76 | |
77 | // 조합할 원소 갯수가 아직 남아있을 경우 |
78 | else |
79 | { |
80 | for (int i = index; i < P.length; i++) |
81 | { |
82 | isChecked[i] = true; |
83 | |
84 | combination(i + 1, count - 1); |
85 | |
86 | isChecked[i] = false; |
87 | } |
88 | } |
89 | } |
90 | |
91 | /** |
92 | * 벡터 계산 함수 |
93 | * |
94 | * @return [double] 벡터 크기 |
95 | */ |
96 | private static double getVector() |
97 | { |
98 | int x = 0; |
99 | int y = 0; |
100 | |
101 | for (int i = 0; i < P.length; i++) |
102 | { |
103 | // 양수로 선택된 점일 경우 |
104 | if (isChecked[i]) |
105 | { |
106 | x += P[i][0]; |
107 | y += P[i][1]; |
108 | } |
109 | |
110 | // 음수로 선택된 점일 경우 |
111 | else |
112 | { |
113 | x -= P[i][0]; |
114 | y -= P[i][1]; |
115 | } |
116 | } |
117 | |
118 | return Math.sqrt(Math.pow(x, 2) + Math.pow(y, 2)); |
119 | } |
120 | } |
분류 🔗
- 수학
- 브루트포스 알고리즘
📆 작성일
2021-06-9 Wed 00:50:26
📚 카테고리
🏷️ 태그