백준 JAVA 17087번 숨바꼭질 6 리뷰

블로그 이전, 2023. 5. 13. 11:41 에 작성했던 글입니다.

 

 

1.나의 코드

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

public 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());

        int[] distance = new int[n];
        st= new StringTokenizer(br.readLine());

        for(int i=0; i<distance.length; i++){ //배열 초기화
            int num=Integer.parseInt(st.nextToken());
            distance[i]=s-num;
            if(s-num<0){
                distance[i]=-(s-num);
            }
        }
        int result=distance[0];
        if(n==1){ //result
            System.out.println(distance[0]);
        }else{
            for(int i=1;i<distance.length; i++){
                result=GCD(result,distance[i]); //최대공약수를 다시 GCD에 넣고 다른 수와 또 최대공약수를 구하기 
                //때문에 GCD() 파라미터 첫번째 값에 result를 넣었다.
            }
            System.out.println(result);
        }

    }
    //유클리드 호제법을 이용한 최대공약수 구하기
    public static int GCD(int a, int b){
        if(b==0){ //종료조건
            return a;
        }else{ //최대공약수 구하고 다시 호출
            return GCD(b,a%b);

        }
    }
}

 

2.나의 풀이

문제를 처음에 이해하지 못해서 잘못된 접근을 했는데 

문제에서  '수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이동할 수 있다. ' 라고 되어있다.

1초마다 D만큼 움직인다, 즉 보폭을 말하는 것이다. 만약 보폭이 3으로 설정되고 수빈이가 0에 있다면 3,6,9,12.... 이렇게 갈 것이다.

 

만약 동생이 한명일 경우 그냥 동생과 수빈이의 차를 구하면 될 것이다.하지만 동생이 여러명일 경우 가장 효율적이고 가장 크게 D(보폭)를 움직이려면 최대공약수가 필요하다.최대공약수는 유클리드 호제법을 이용해서 푼다.

 

<유클리드 호제법>

예를 들어 1071, 1029 최대공약수 구한다면 아래의 흐름을 통해 최대공약수를 구할 수 있다.

 

1071%1029=42

           1029%42=21

                      42%21=0

                              21%0 ....

 

최대공약수 21

 

현재 나누는 수가 다음에 나누어지는 수가 되고 현재 1071/1029의 나머지가 다음 나누는 수가 된다.

나머지가 0이 되면 나누는 수가 최대공약수가 된다.

풀어쓰니까 어려워보이는데 위의 흐름으로 이해하면 쉽게 이해가 될 것이다.

 

<대소관계 비교>

GCD(a,b) 함수를 통해 만들면 되는데 a%b를 하는 과정에서 대소관계 비교는 필요하지 않다.

a%b=c 이면 c 항상 b보다 작은 성질이 있다. 나머지는 나누는 수보다 항상 작다.

위의 흐름을 다시 보자. 나누는 수가 나누어지는 수로 가고 나머지가 나누는 수로 간다.

이 과정에서 항상 나누어지는 수>나누는 수(나머지)가 되기때문에 따로 대소 비교를 하지 않아도 된다.

 

재귀함수를 통해서 호출한다. 나머지는 코드를 참고하면 된다.