17087.숨바꼭질6

문제

수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다.

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

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

입력

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

출력

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

풀이

알고리즘 흐름

문제에서 주어지는 값들이 조금 모호하게 적혀있다. 여기서 말하는 D는 수빈이가 한번에 움직일수있는 보폭으로 보는것이 맞다.

예를들어 D값이 2이면 2,4,6,8... 로만 움직일수 있는것이고, 13이면 13,26,39...으로 움직일수있는것이다.

이것을 대입하면 문제를 풀수있다. 예제를 통해 예를 들어보자.

1 O 3 O O O 7 O O O 11

• 수빈이는 3번에서 출발한다.
• 보폭D로 양쪽으로 움직이며 모든 동생(1,7,11)을 찾으려면 D = 2일것이다.
• 1까지 abs(3-2)로 방문 가능하고, 7까지 abs(3+2*2)로 방문하고, 11까지 abs(3+2*4)로 방문이 가능하다.

코드

첫번째 시도

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  

public class 숨바꼭질6 {  
    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  

        String[] split = br.readLine().split(" ");  

        int n = Integer.parseInt(split[0]); //동생의 수  
        int subin = Integer.parseInt(split[1]); //수빈이 위치  

        String[] split1 = br.readLine().split(" ");  

        int res = 0;  

        int[] arr = new int[n];  

        for(int i=0; i<n; i++){  
            //수빈이와 동생의 위치의 차를 구해준다.  
            int brother = Integer.parseInt(split1[i]);  
            arr[i] = Math.abs(brother-subin);  
        }  

        if(n == 1){  
            res = Math.abs(arr[0]-subin);
        }else {  
            res = arr[0];  
            for(int i=1; i<n; i++){  
                res = gcd(res,arr[i]);  
            }  
        }  

        System.out.println(res);  
        br.close();  
    }  

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

결과를 보니 실패하였다.
자세히보니 if(n == 1){res = Math.abs(arr[0]-subin); 이부분이 문제였다. 위에서 arr[0]에서 이미 abs값을 구해놓고 한번더 계산하고 있었다... 바보

두번째시도

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  

public class 숨바꼭질6 {  
    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  

        String[] split = br.readLine().split(" ");  

        int n = Integer.parseInt(split[0]); //동생의 수  
        int subin = Integer.parseInt(split[1]); //수빈이 위치  

        String[] split1 = br.readLine().split(" ");  

        int res = 0;  

        int[] arr = new int[n];  

        for(int i=0; i<n; i++){  
            //수빈이와 동생의 위치의 차를 구해준다.  
            int brother = Integer.parseInt(split1[i]);  
            arr[i] = Math.abs(brother-subin);  
        }  
        res = arr[0];  

        if(n != 1){  
            for(int i=1; i<n; i++){  
                res = gcd(res,arr[i]);  
            }  
        }  

        System.out.println(res);  
        br.close();  
    }  

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

성공!

답을 안찾아보고는 풀기 어려운 문제였다. 문제를 보고 최대공약수를 구해야하는 문제라는것을 생각할수있을때까지 연습해야 되겠다.