Problem Solving/Java
백준 17087 숨바꼭질 6 문제풀이 ( Java )
TakeKnowledge
2019. 10. 22. 21:25
반응형
17087번: 숨바꼭질 6
수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다. 수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이동할 수 있다. 수빈이의 위치가 동생이 있는 위치와 같으면, 동생을 찾았다고 한다. 모든 동생을 찾기위해 D의 값을 정하려고 한다. 가능한 D의 최댓값을 구해보자.
www.acmicpc.net
|
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
|
public class Main {
static int gcd(int a, int b) {
if (b == 0) {
return a;
} else {
return gcd(b, a % b);
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
// reader writer 생성
String[] info = br.readLine().split(" ");
// info[0]에 N / info[1]에 S
String[] temp = br.readLine().split(" ");
int[] distance = new int[temp.length];
for (int i = 0; i < temp.length; i++) {
if (Integer.parseInt(temp[i]) > Integer.parseInt(info[1])) {
distance[i] = Integer.parseInt(temp[i]) - Integer.parseInt(info[1]);
} else {
distance[i] = Integer.parseInt(info[1]) - Integer.parseInt(temp[i]);
}
}
int brothersCnt = Integer.parseInt(info[0]);
int answer = distance[0];
if (brothersCnt != 1) {
// 동생이 한명이 아니면 최대 공약수를 구한다
for (int i = 1; i < distance.length; i++) {
answer = gcd(answer, distance[i]);
}
}
}
}
|
이건 솔직히 문제를 좀 모호하게 적어놨다
D가 수빈이가 한번에 움직일 수 걸음의 보폭(?) 이다
예를 들어 4면 4 , 8 , 12 , 16... 이런 식으로만 움직일 수 있고, 5면 5, 10, 15 ,20 .. 이런 식으로만 움직일 수 있다
이 점만 명확해지면 최대 공약수로 풀 수 있다.
여러개의 최대공약수도 결국은 두 수의 최대 공약수를 구하는 것과 같다
예를 들어 a, b , c ,d 가 있다고 치면
a와 b의 최대공약수와 c 사이의 최대 공약수를 구해서 그것과 d의 최대 공약수를 구하면
a, b, c, d의 최대 공약수가 나온다
반응형