백준 17087번 숨바꼭질 6 자바 Java (☆공부 250일차)

17087 숨바꼭질 6

https://www.acmicpc.net/problem/17087

17087번: 숨바꼭질 6

 

 

 

---

백준 17087번 문제 숨바꼭질 6

---

문제

---

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	512 MB	8028	3973	3186	48.478%

문제

수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A₁, A₂, ..., A_N에 있다.

수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이동할 수 있다. 수빈이의 위치가 동생이 있는 위치와 같으면, 동생을 찾았다고 한다.

모든 동생을 찾기위해 D의 값을 정하려고 한다. 가능한 D의 최댓값을 구해보자.

입력

첫째 줄에 N(1 ≤ N ≤ 10⁵)과 S(1 ≤ S ≤ 10⁹)가 주어진다. 둘째 줄에 동생의 위치 A_i(1 ≤ A_i ≤ 10⁹)가 주어진다. 동생의 위치는 모두 다르며, 수빈이의 위치와 같지 않다.

출력

가능한 D값의 최댓값을 출력한다.

제한

 

예제 입력 1

3 3
1 7 11

예제 출력 1

2

예제 입력 2

3 81
33 105 57

예제 출력 2

24

예제 입력 3

1 1
1000000000

예제 출력 3

999999999

힌트

 

 

 

 

---

과정 생각해보기

---

 

 

https://gimbalja.tistory.com/192

공부 111일차: 백준 17087번 숨바꼭질 6 자바 java

4달 전에 푼 문제(풀이가 괜찮아서 그대로..)

 

 

처음엔 좀 당황했는데.. '최댓값'을 구하라는 이야기에 최대공약수로 접근해보면 될 것 같다

동생들 사이의 거리들로 해보려다가, 수빈이의 위치에서 +-D를 하는 것이기 때문에 각 위치와의 거리를 구해보기로 했다(최대공약수를 구해야 하므로 뺀 값은 절댓값으로 저장해야 한다)이후 그 거리끼리의 최대공약수를 구하면 문제에서 요구하는 값이 나온다

 

1. 최대공약수 도출 메서드 구하기

https://gimbalja.tistory.com/173

공부 94일차: 백준 2609번 최대공약수와 최소공배수 자바 java

gcd를 최대공약수로, 위의 링크에 유클리드 호제법으로 간단하게 최대공약수를 구현하는 방법을 설명해두었다

 

 

2. n개 숫자의 최대공약수 구하기이때, n개의 거리가 나오므로 n개의 수의 최대공약수를 구해야 한다

최대공약수를 구하는 함수가 gcd(n1, n2)일 때, 3개 이상의 숫자의 최대공약수는 다음과 같이 구한다

 

숫자가

3개일 때: gcd(gcd(a, b), c)

4개일 때: gcd(gcd(gcd(a, b), c), d )

5개일 때: gcd(gcd(gcd(gcd(a,b),c),d),e)

...

이렇게 앞의 숫자들의 최대공약수와 뒤 숫자의 최대공약수를 구하면 된다

 

 

정리한 과정은 아래와 같다

 

1. n과 s를 받는다

2. n만큼 반복문을 돌린다

　2-1. 각 거리 - s를 빼서 배열에 넣는다

3. ArrayList에 넣은 거리들의 최대공약수를 구한다

 

 

 

---

정답 인정 코드

---

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st1 = new StringTokenizer(br.readLine());
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        
        int n = Integer.parseInt(st1.nextToken());
        int s = Integer.parseInt(st1.nextToken());
        int[] siblings = new int[n];
        
        for(int i = 0; i < n; i++) {
            siblings[i] = Math.abs(Integer.parseInt(st2.nextToken())-s);
        }
        
        int result = siblings[0];    // ★
        for(int i = 1; i < n; i++) {
            result = gcd(result, siblings[i]);
        }
        
        System.out.println(result);
    }
 
    static int gcd(int x, int y) {
        if(x % y == 0) {
            return y;
        }
        return gcd(y, x%y);
    }
}
 

 

 

 

---

맞은 문제 순서대로

BufferedReader + StringTokenizer + 배열

BufferedReader + StringTokenizer + ArrayList

Scanner + ArrayList

 

이제 보니 동적 배열을 쓸 이유가 없기 때문에 정적 배열로 선언

그래서 가장 최근 풀이에서 메모리와 시간이 줄었다

 

(나중에 한 번 더 비트마스킹으로 풀어보기)