[백준] JAVA 자바 : 숨바꼭질 6 (17087번)

---

수빈이의 현재 위치에서 동생들을 모두 찾을 수 있는 D의 최댓값을 구하는 문제이다.
사실 처음에는 되게 막막했는데… 예제 출력들의 공통된 패턴을 찾아본 결과, 동생들의 위치와 수빈이의 현재 위치의 차이(거리)의 최대공약수들 중 가장 작은 값이라는 점이었기에 그걸 구하면 된다.

사실 처음에는 동생들의 위치가 주어지면 그 중 가장 작은 값을 가지고 나머지 거리들과의 최대공약수를 구하려고 min을 선언했는데, 사실 굳이 그럴 필요가 없었다. 가장 작은 값이 아니라도 그냥 아무 거리나 잡고 그 값과 다른 거리들의 최대공약수 중 가장 작은 값을 구하기만 하면 됐다. 어차피 다 공통된 최대공약수를 구하는 것이기 때문에…

 

import java.io.*;
import java.util.StringTokenizer;

public class Hiding {
    
    public static int stoi(String str) {
        return Integer.parseInt(str);
    }
    
    public static int GCD(int n1, int n2) {
        if (n1 % n2 == 0) return n2;
        
        return GCD(n2, n1%n2);
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = stoi(st.nextToken()); // 동생의 개수
        int S = stoi(st.nextToken()); // 수빈이의 현재 위치
        
        int[] s_list = new int[N];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i=0; i<N; i++) {
            s_list[i] = stoi(st.nextToken());
            s_list[i] = Math.abs(s_list[i]-S);
        } // 각 배열에 수빈이의 현재 위치에서 동생들의 위치를 뺀 값의 절댓값(거리)을 저장한다.
        
        int min = s_list[0]; // 첫 번째 거리 하나 가지고
        
        // 그 거리와 다른 거리들의 최대공약수 중 가장 작은 값을 찾은 후 반환
        for (int i=1; i<s_list.length; i++) {
            int tmp;
            tmp = GCD(min, s_list[i]);
            if (min > tmp) {
                min = tmp;
            }
        }
        System.out.println(min);
        
        br.close();
    }
}

 

로그인

 

 

작성일자: 2023-09-15