백준 17087번: 숨바꼭질 6 with Java

숨바꼭질 6

 

 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

512 MB

12560

6332

5085

49.427%

문제

수빈이는 동생 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값의 최댓값을 출력한다.

예제 입력 1 복사

3 3
1 7 11

예제 출력 1 복사

2

예제 입력 2 복사

3 81
33 105 57

예제 출력 2 복사

24

예제 입력 3 복사

1 1
1000000000

예제 출력 3 복사

999999999

 

 

---

 

 

글 쓰기가 왜 이렇게 힘든거야...

이 문제를 택한 이유: 뭔가 재밌어 보여서.

수빈이는 동생 N명과 숨바꼭질을 하고 있다고 한다.. 수빈이는 동생이 많나보다...

곧바로 깨닫게 되었다. 이 문제는 재미가 없다.

그래도 이미 글을 쓰기 시작했으니 어쩔 수 없이 이 문제를 풀어야 한다...

근데 아니 진심 뭔 소린지 모르겠는데 개큰일

 

자.. 입출력을 보자

N과 S... 동생 개수랑 수빈이 위치...

그 담에 동생들 위치...가 N개 들어오겠네

 

구해야 하는 건??? X - D X + D 해서 동생 다 찾을 수 있는 최대값 D

 

와 문제 이해 완료

그런데 어떻게 풀지 이걸???

동생 있는 위치랑 차이 내서 이동시켜주기.....? 하 내 힘들다

아 잠만 저거 내 위치랑 동생들 위치를 뺀 절대값끼리 뭐 어떻게 해보는 거 아닐까... 그 최대공약수를 찾는 거지 어 음

시도 갑니데이

 

아 잠만 입력부터 난관 이거 두 개 들어올 때 분리 어케햇지

StringTokenizer로 해결완.

 

숫자가 여러 개일 때 최대공약수는... 어떻게 찾는담.... 

일단 정렬한 담에 앞에 숫자 갖고 어케 해보기...?

 

1. 정렬된 가장 작은 수부터 1까지 돌려보기

package Week01.BJ_17087;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());  // 동생 수
        int S = Integer.parseInt(st.nextToken());  // 수빈 위치

        st = new StringTokenizer(br.readLine());
        int[] distance = new int[N];  // 동생들과의 거리
        for (int i = 0; i < N; i++) {
            int tmp = Integer.parseInt(st.nextToken());
            if (tmp > S) {
                distance[i] = tmp - S;
            } else {
                distance[i] = S - tmp;
            }
        }
        Arrays.sort(distance);  // 정렬

        int answer = getGCD(distance);
        System.out.println(answer);
    }

    static int getGCD(int [] arr) {
        if (arr.length == 1) {
            return arr[0];
        }

        int n = arr[0];
        for (int i = n; i >= 1; i--) {
            boolean flag = true;
            for (int a : arr) {
                if (a % i != 0) {
                    flag = false;
                    break;
                }
            }

            if (flag) {
                return n;
            }
        }

        return 1;
    }
}

 

 

뭔데...?

런타임 에러 뭔데

아 보니까 n 리턴해서 그런가 ㅎㅎㅎ

package Week01.BJ_17087;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());  // 동생 수
        int S = Integer.parseInt(st.nextToken());  // 수빈 위치

        st = new StringTokenizer(br.readLine());
        int[] distance = new int[N];  // 동생들과의 거리
        for (int i = 0; i < N; i++) {
            int tmp = Integer.parseInt(st.nextToken());
            if (tmp > S) {
                distance[i] = tmp - S;
            } else {
                distance[i] = S - tmp;
            }
        }
        Arrays.sort(distance);  // 정렬

        int answer = getGCD(distance);
        System.out.println(answer);
    }

    static int getGCD(int [] arr) {
        if (arr.length == 1) {
            return arr[0];
        }

        int n = arr[0];
        for (int i = n; i >= 1; i--) {
            boolean flag = true;
            for (int a : arr) {
                if (a % i != 0) {
                    flag = false;
                    break;
                }
            }

            if (flag) {
                return i;
            }
        }

        return 1;
    }
}

 

 하고 return i 해줬는데도

 

헤이,, 왓츠롱윗유,,,

 

걍 하나씩 하는 게 문제인 것 같다.

답은 

유클리드 호제법

 

네...

 

두 수의 최대공약수(GCD)를 매우 빠르게 구하는 알고리즘이라고 한다.

 

두 수 a, b의 최대공약수는 b와 a % b의 최대공약수와 같다.

gcd(a, b) = gcd(b, a % b)
이걸 b가 0이 될 때까지 반복하면, 그때의 a가 최대공약수가 된다.

 

    static int gcd(int a, int b) {
        while (b != 0) {       // b가 0이 될 때까지 반복
            int tmp = a % b;   // a를 b로 나눈 나머지를 임시 저장
            a = b;             // b를 a에 저장
            b = tmp;           // 나머지를 b에 저장
        }
        return a;  // b가 0이 되면 a가 최대공약수
    }

 

반복문으로 구현했는데, 재귀로도 가능하다고 한다... 

암튼 

1. a랑 b를 뽑는다.

2. a 를 b로 나눈다. 나머지는 임시 저장

3. b를 a에 저장한다.

4. 나머지를 b에 저장한다.

-> 이걸 b가 0 될 때까지 하고 a가 최대공약수가 된단다.

 

    static int getGCD(int[] arr) {
        int result = arr[0];  // 첫 번째 값을 기준으로 시작
        for (int i = 1; i < arr.length; i++) {
            result = gcd(result, arr[i]);  // 순차적으로 최대공약수 계산
        }
        return result;
    }

 

이건 코드 조건이 배열이었기 때문에,,

첫 번째 값을 기준으로 시작해서 2개씩 계속 비교한다!

 

 

 

하

쫌 어이없는 거

package Week01.BJ_17087;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());  // 동생 수
        int S = Integer.parseInt(st.nextToken());  // 수빈 위치

        st = new StringTokenizer(br.readLine());
        int[] distance = new int[N];  // 동생들과의 거리
        for (int i = 0; i < N; i++) {
            int tmp = Integer.parseInt(st.nextToken());
            if (tmp > S) {
                distance[i] = tmp - S;
            } else {
                distance[i] = S - tmp;
            }
        }
        Arrays.sort(distance);  // 정렬

        int answer = getGCD(distance);
        System.out.println(answer);
    }

    static int getGCD(int[] arr) {
        int result = arr[0];
        for (int i = 1; i < arr.length; i++) {
            result = gcd(result, arr[i]);
        }
        return result;
    }

    static int gcd(int a, int b) {
        while (b != 0) {
            int tmp = a % b;
            a = b;
            b = tmp;
        }
        return a;
    }
}

 

검색해서 갖다 붙인 것도 

 

???????????????

찾아보니까 걍 패키지를 안 지우고 돌려서 나는 오류였다..

지우고 돌려보니까 하나씩 하는 것도 돌아가긴 하더라

 

 

메모리 차이는 의외로 별로 안 났고 시간 차이는 쫌 컸다.

집 가서 유클리드 호제법 찾아보고.. 정리해야지