2981번

https://www.acmicpc.net/problem/2981

2981번: 검문

이 문제를 풀면서 내가 수학과 규칙성 찾기가 많이 부족하구나를 느꼈다...

처음에 이 문제를 시도했을 때는 단순 하드 코딩 밖에 생각나지 않았다.. 그래서 바로 메모리 초과로 뚜드려 맞고 고민을 해보았다.

그런데 도저히 방도가 생각나지 않았다. 그래서 이제 미지수를 두어서 여러가지 시도를 해보았다.

미지수를 두고 방정식을 세워서 더해도 보고, 빼보기도 하면서 무언가 감이 올듯 오지 않아서 결국 또 질문 게시판을 향했다..

그래서 게시판에서 다른 사람들의 질문을 보면서 감을 잡고 문제를 풀어서 해결을 했다.

그 후 다른 사람들의 블로그에 가서 이 문제의 원리를 알아보았다.

 

내가 미지수를 두고 접근하는 방식은 좋았었다.

다만 찾지 못했을 뿐..

수식을 써서 생각해보면(M=나눈 수, L=나머지)라고 정의 했을 때

위 사진처럼 표현할 수 있다.

여기서 A1과 A2를 빼면 L은 사라지고 M*(a1-a2)만 남는다. 따라서 M은 (a1-a2)의 약수이다.

즉, M은 공약수이다. 생각해보면 문제에 조건이 있다.

나머지가 모두 같게 되는 M을 찾으려고 한다. 즉, 모두 같은 M을 갖는다.

따라서 주어진 수는 어떠한 공약수에 L을 더한 것이다.

 

따라서 주어진 수들 간의 차들의 공약수를 구하면 된다.

여기서 주의할 것은 수들을 정렬해줘야한다. - 이 부분의 이유는 아직 학습중이다..아시는분 있으면 댓글 좀 달아주세요ㅠㅠ

그렇게 해서 두수의 차들의 최대 공약수를 구하는 방법으로 유클리드 호제법을 적용해서 해결했다.

package backjoon;

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

public class b2981 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        ArrayList<Integer> ar = new ArrayList<>();
        for(int i=0; i<N; i++){
            arr[i]= Integer.parseInt(br.readLine());
        }
        for(int i=0; i<N-1;i++){
            ar.add(Math.abs(arr[i]-arr[i+1]));
        }
        ar.sort(Integer::compareTo);

        int prev = 0;
        if(ar.size()>2){
            prev = gcd(ar.get(0),ar.get(1));
            for(int i=2; i<N-1; i++){
                prev=gcd(prev,ar.get(i));
            }
        }else {
            prev=ar.get(0);
        }

        StringBuilder sb = new StringBuilder();
        for(int i=2; i<=prev; i++){
            if(prev%i==0){
                sb.append(i).append(" ");
            }
        }
        System.out.println(sb);
    }
    public static int gcd(int a, int b){
        if(b==0){
            return a;
        }
       return gcd(b,a%b);
    }
}