𝝅번째 알파카의 개발 낙서장

screen

[백준 / JAVA] 백준 알고리즘 1007번 벡터

posts

알고리즘

시리즈 톺아보기

백준 알고리즘

백준 알고리즘
count

습격자 초라기 🔗

랭크 사용 언어
image JAVA

🔗 전체 1007번 문제

조건 🔗

시간제한 메모리 제한
2초 512MB

문제 🔗

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

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

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

입력 🔗

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

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

출력 🔗

각 테스트 케이스마다 정답을 출력한다. 절대/상대 오차는 까지 허용한다.

케이스 🔗

예제 1 🔗

  • 입력

TC

02
14
25 5
35 -5
4-5 5
5-5 -5
62
7-100000 -100000
8100000 100000
  • 출력

TC

00.000000000000
1282842.712474619038

풀이 🔗

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

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

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

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

image

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

위 식으로 계산한 값의 최소값이 알고리즘의 해답이 된다. 즉, 우리는 을 조건에 맞게 조합해야한다. 각 조합의 를 계산한 뒤, 이 중 최소값을 반환하면 될 것 같다.

무턱대고 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

0import java.io.BufferedReader;
1import java.io.IOException;
2import 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 */
11public 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}

분류 🔗

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