BOJ 2981) 검문

문제

트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다.

상근이는 시간을 때우기 위해서 수학 게임을 하기로 했다.

먼저 근처에 보이는 숫자 N개를 종이에 적는다. 그 다음, 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다. M은 1보다 커야 한다.

N개의 수가 주어졌을 때, 가능한 M을 모두 찾는 프로그램을 작성하시오.

입력

첫째 줄에 종이에 적은 수의 개수 N이 주어진다. (2 ≤ N ≤ 100)

다음 줄부터 N개 줄에는 종이에 적은 수가 하나씩 주어진다. 이 수는 모두 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. 같은 수가 두 번 이상 주어지지 않는다.

항상 M이 하나 이상 존재하는 경우만 입력으로 주어진다.

출력

첫째 줄에 가능한 M을 공백으로 구분하여 모두 출력한다. 이때, M은 증가하는 순서이어야 한다.

 

전개

 일단 N개의 숫자에 순서가 존재하지 않고, 모든 M을 찾아야 하므로 모든 N개의 입력값에 대해 최대 크기 미만의 수를 검사해야 한다는 생각과 함께, 최악의 경우 10억에 가까운 수 100개를 검사해야 하므로 시간복잡도가 1000억이므로 일일히 검사해서는 시간초과가 발생할 것이라는 생각이 듬. 

 그렇다면 입력값에 대해서 필터링이 가능한가? 입력값 사이에 배수관계와 같은 특별한 관계가 존재하더라도 임의의 M으로 나누었을 때 나머지가 같게 되는 규칙이 생각나지 않는다.

 

1.

import java.util.Scanner;

public class Main {

    static int[] arr;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        arr = new int[N+1];
        for(int i=1; i<=N; i++)
            arr[i] = sc.nextInt();

        for(int i=2; i<=arr[N]; i++) { //나누는 수
            for(int j=2; j<=N; j++) { //이걸 %연산
                if(arr[j]%i!=arr[j-1]%i)
                    break;
                if(j==N) System.out.println(i);
            }
        }

    }
}

> 이렇게 2부터 arr[N]까지 단순 모듈러연산을 통해 나머지를 비교할 경우 시간 초과가 발생한다.

 

2.

 처음 생각난 규칙은 입력값이 M보다 작을 경우 나머지는 입력값 자체가 된다. 따라서 N개의 입력값중 최소값을 N[0]이라고 하면, M이 N[0]보다 클 경우 N[1]보다는 작아야 한다. (같은 수가 두번이상 주어지지 않는다고 하였으므로 N[0]!=N[1])

그렇다고 해도 N[0]이 10억에 가까운 수라면 시간복잡도가 1000억에 가깝다는 것은 변하지 않는다.

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        //int[] tmp = new int[N];
        int[] arr = new int[N];
        for(int i=0; i<N; i++)
            arr[i] = sc.nextInt();
        Arrays.sort(arr);

        for(int i=2; i<=arr[1]; i++) { //나누는 수
            for(int j=1; j<N; j++) { //이걸 %연산
                if(arr[j]%i!=arr[j-1]%i)
                    break;
                if(j==N-1) System.out.print(i+" ");
            }
        }
    }
}

> 나누는 범위가 경우에 따라 확실하게 줄 수도 있지만, 최악의 경우 시간복잡도가 매우 크다.

 

M의 후보가 되는 개수를 확실하게 줄일 수 있는 방법은 없을까?

 

----------------------------------------------------------------------------------------------------------------------------

겨울에 생각하다 못풀고, 지금도 생각했는데도 못풀어서 해답을 보니 수학 개념(유클리드 호제법)이 필요한 문제이다.

옛날에 gcd, lcm문제 풀때 봤던것같은데 이번에 확실하게 정리해놓자

https://eckrin.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C-%ED%98%B8%EC%A0%9C%EB%B2%95 

 

모든 숫자들의 차이에 대해서 최대공약수를 구하고, 최대공약수의 약수를 출력해주면 된다.

 

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] arr = new int[N];
        for(int i=0; i<N; i++)
            arr[i] = sc.nextInt();
        Arrays.sort(arr);

        int val = arr[1]-arr[0];
        for(int i=2; i<N; i++) {
            val = gcd(val, arr[i]-arr[i-1]);
        }

        for(int i=2; i<=val; i++) {
            if(val%i==0)
                System.out.print(i+" ");
        }
    }

    static int gcd(int a, int b) { //a>b
        if(b==0)
            return 0;
        if(a<b) {
            int tmp = b;
            b = a;
            a = tmp;
        }
        if(a%b==0)
            return b;
        return gcd(b, a%b);
    }
}