반응형
🔺 문제
🔺 코드
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
|
import java.util.*;
import java.io.*;
class Point {
int x, y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
Point[] points = new Point[N];
for(int i = 0 ; i < N ; i++) {
st = new StringTokenizer(br.readLine(), " ");
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
points[i] = new Point(x, y);
}
int diff = Integer.MAX_VALUE;
for(int i = 0 ; i < N - 1 ; i++) { // 모든 쌍에 대해 조사
for(int j = i + 1 ; j < N ; j++) {
int tmp = getDist(points[i], points[j]);
diff = Math.min(diff, tmp); // 최솟값 갱신
}
}
System.out.println(diff);
}
// 두 점 사이 거리 반환 메소드
public static int getDist(Point a, Point b) {
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
}
|
cs |
🧩 해결 아이디어
• 완전 탐색 (물체 단위)
- 모든 쌍에 대해 전부 거리를 조사하여 그 중 제곱의 최솟값을 구한다.
- 시간 복잡도 : O(N^2)
🔺 다른 풀이들
- 점을 클래스로 받지 않고, 배열 2개를 만들어 x좌표와 y좌표 값을 저장했다.
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
|
import java.util.Scanner;
public class Main {
public static final int INT_MAX = Integer.MAX_VALUE;
public static final int MAX_N = 100;
public static int n;
public static int[] x = new int[MAX_N];
public static int[] y = new int[MAX_N];
// 두 점 사이의 거리의 제곱 값 반환
public static int dist(int i, int j) {
return (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
for(int i = 0; i < n; i++) {
x[i] = sc.nextInt();
y[i] = sc.nextInt();
}
// 모든 쌍에 대해서 거리 제곱값을 계산해 그 중 최솟값 탐색
int minDist = INT_MAX;
for(int i = 0; i < n; i++)
for(int j = i + 1; j < n; j++)
minDist = Math.min(minDist, dist(i, j));
System.out.println(minDist);
}
}
|
cs |
- 분할 정복도 가능하다구....
💬 느낀 점
간단한 문제를 너무 오래 고민해버렸다는ㄴ......
뇌가 진짜 이상하다...
일찍 자야겠다....
1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
V |
(참고)
✔ 백준 2261번과 유사하다 함!
반응형
'코테 > 코드트리' 카테고리의 다른 글
[코드트리/NOVICE MID] 최소 넓이 (JAVA) (0) | 2023.11.15 |
---|---|
[코드트리/NOVICE MID] 색종이의 총 넓이 (JAVA) (0) | 2023.11.15 |
[코드트리/NOVICE MID] 밭의 높이를 고르게하기 (JAVA) (0) | 2023.11.13 |
[코드트리/NOVICE MID] 개발팀의 능력 (JAVA) (0) | 2023.11.12 |
[코드트리/NOVICE MID] 개발자의 능력 2 (JAVA) (0) | 2023.11.12 |