22. 17087번 숨바꼭질6

문제가 알아듣기 힘들었는데 간단히 설명하면

수빈이는 X+D, X-D만큼 움직일수있다.

 

첫번째 입력받는 n은 동생의 수

두번째 입력받는 S는 수빈이의 위치

세번째 입력받는 수들은 동생(들)의 위치

 

출력되어야 하는 수 D는 수빈이의 한번 움직일때의 발걸음 수

 

이 문제는 수빈이와 동생(들)의 위치사이의 거리를 구해 각 위치들을 모두 만날수 있는 수를 찾으라는 문제이다.

예제 2번을 예시로 든다면

S(수빈이의 위치) 81 과 동생(들)의 위치 33, 105, 57 사이의 거리를 구한다.

동생들의 위치는 수빈이의 위치보다 작거나 클수 있기때문에 해당 거리를 구하기 위해서는 절대값을 이용한다.

나온 거리는 48, 24, 24 가 되겠고 이 수들을 모두 걸칠수 있는 수빈이의 발걸음 수 들 중 가장 큰 수를 구하면 그것이 정답이 된다. 즉, 최대 공약수를 구하라는 말이 되겠다.

 

1. 우선 수빈이와 동생들간의 거리를 구한다 [절대값 이용]

2. 해당 수들의 최대공약수를 구한다.

 

 

0. 기본 설정

public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        int S = Integer.parseInt(st.nextToken());

첫 입력받는 두 숫자를 토큰화 시켜 각각 N과 S로 정의한다

 

int[] arr = new int[N];
st = new StringTokenizer(br.readLine(), " ");

배열 arr는 동생들의 수만큼의 크기를 가진다.

또한 동생들을 각각 배열안에 넣기위해 토큰화를 한다

for (int i = 0; i < N; i++) {
	arr[i] = Integer.parseInt(st.nextToken());
}

토큰화 후 배열에 반복문으로 넣어준다. arr[i] 는 동생들의 수만큼 크기를 가지고있고

위 반복문을 통해 동생들의 위치를 넣어 준다

 

1-1. 수빈이와 동생들간의 거리를 구한다.

int distance = Math.abs(arr[0] - S);

Math.abs는 () 에 들어갈 수의 절대값을 표현해준다 

ex) Math.abs(-1) = 1 , Math.abs(1) = 1

 

1-2. 동생이 한명일땐 위와 같은 식을 쓰면되지만 여러명일땐 반복문을 써준다 따라서

 if (N > 1) {
    for (int i = 1; i < N; i++) {
    distance = GCD(distance, Math.abs(arr[i] - S));
    }
}

이 경우는 동생이 2명이상 이기에 최대 공약수를 구해야한다.

 

2. 각 수들의 최대공약수를 구한다.

public static int GCD(int a, int b) {
    if (a == 0) {
    return b;
    } else {
    return GCD(b % a, a);
    }
}

두수의 최대공약수를 구하는식

 

3. 코드전문

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class training {

    public static int GCD(int a, int b) {
        if (a == 0) {
            return b;
        } else {
            return GCD(b % a, a);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        int S = Integer.parseInt(st.nextToken());
        int[] arr = new int[N];

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        //동생이 한명일 경우
        int distance = Math.abs(arr[0] - S);

        //동생이 한명보다 많을경우 최대공약수 찾기
        if (N > 1) {
            for (int i = 1; i < N; i++) {
                distance = GCD(distance, Math.abs(arr[i] - S));
            }
        }
        bw.write(String.valueOf(distance));

        bw.flush();
        bw.close();
    }
}

 

결과