[백준2981번] 검문

문제

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

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

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

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

입력

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

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

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

출력

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

예제 입력 1

3
6
34
38

예제 출력 1

2 4

나의 풀이

처음에 이 문제를 접근할 때에는 나머지는 0과 같거나 크고 입력으로 주어지는 수들 중 가장 작은 수보다는 작아야하니까 입력되는 N개의 수들을 오름차순으로 정렬을 하고 두 번째로 큰 수까지 반복을 하며 만약 나머지가 가장 작은 수보다 크면 바로 continue를 하고 그렇지 않으면 모두 계산을 해가면서 나머지가 같은지를 확인했었다. 이러면 중첩 for문이 나오면서 시간복잡도가 O(n제곱)이었고 역시나 시간초과가 나왔다.

그래서 해법을 검색으로 찾아보았다. 우선 입력으로 주어지는 배열을 nums라 해보겠다. 그럼 nums[i] = m(몫) * tmp[i] + r(나머지)와 같이 나타낼 수가 있다. 여기서 문제는 나머지가 같을때다. 이 나머지 r만 없으면 m*tmp[i]가 되어 m의 배수가 된다는 것을 알 수 있다. 이러한 식을 얻기위해서 nums[i] - nums[i-1]을 하는 방법이 있었다. 이렇게 값을 빼주게 되면 식이 다음과 같게된다. nums[i] - nums[i-1] = m * (tmp[i] - tmp[i-1]) + (r-r) 따라서 r이 없어지고 m * (tmp[i] - tmp[i-1])만이 남게 되면서 자연스럽게 m의 배수가 된다. (여기서 처음에 잘 이해가 가지않았다. 왜 갑자기 r-r이지? 나머지가 다를수도 있지않나? 하지만 조금만 생각해보면 우리는 아직 특정 m을 정하지도 않았기때문에 r이 정해지지 않는다 단지 저렇게 가정하고 가능한 m을 찾는 것이다.) 그럼 이제 전체의 숫자들의 차이(nums[i]-nums[i-1])들의 최대공약수를 구해서 최대공약수의 약수들을 출력해주면 문제는 풀 수 있게된다. (왜 최대공약수를? 인접한 두 수들의 차이는 모두 같지가 않다. 그런데 우리는 그 차이값들을 같은 수로 나누어떨어지는 m들을 찾는 것이다. 그러니 최대로 큰 공약수를 찾은 후 이 최대공약수의 약수들을 구하면 약수들이 모두 m을 대체할 수 있지않는가?!)

단계별 문제풀이에서 수학3에 있는만큼 이 문제는 수학 식을 활용해야대는 문제였다. 처음에 이 생각을 전혀하지 못하여서 접근이 어려웠던 것 같다.

코드

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

/**
 * 2981번 검문
 */
public class Baeckjun2981 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int[] nums = new int[n+1];
        for (int i=1; i<=n; i++) {
            nums[i] = sc.nextInt();
        }

        Arrays.sort(nums);

        int gcd = nums[2] - nums[1];
        for (int i=3; i<=n; i++) {
            gcd = findGcd(Math.max(gcd, nums[i] - nums[i-1]), 
                              Math.min(gcd, nums[i] - nums[i-1]));
        }

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

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

    // 시간초과
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        int n = sc.nextInt();
//
//        int[] nums = new int[n+1];
//        for (int i=1; i<=n; i++) {
//            nums[i] = sc.nextInt();
//        }
//
//        Arrays.sort(nums);
//
//        for (int i=2; i<=nums[2]; i++) {
//            int remainder = nums[1] % i;
//            if (remainder > nums[1]) continue;
//
//            boolean isSame = true;
//            for (int j=2; j<nums.length; j++) {
//                if (remainder != nums[j] % i) {
//                    isSame = false;
//                    break;
//                }
//            }
//
//            if (isSame) {
//                System.out.print(i);
//                System.out.print(' ');
//            }
//        }
//    }
}