[백준] 2981번. 검문(JAVA)

문제

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

---

풀이(45분)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;
import java.util.Collections;

public class Main {        
    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];
        
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(arr); // 정렬

        int gcdVal = arr[1] - arr[0]; // 음수가 되지 않도록 큰 수에서 작은 수로 빼준다.

        for (int i = 2; i < N; i++) {
            // 직전의 최대 공약수와 다음 수(arr[i] - arr[i - 1])의 최대공약수를 갱신 
            gcdVal = gcd(gcdVal, arr[i] - arr[i - 1]);
        }

        // 약수를 저장할 리스트
        List<Integer> divisors = new ArrayList<>();
        
        // 최대공약수의 약수들 찾기 (절반까지만 탐색, 제곱근까지)
        for (int i = 2; i <= Math.sqrt(gcdVal); i++) {
            if (gcdVal % i == 0) {
                divisors.add(i); // 작은 약수
                if (i != gcdVal / i) {  // 제곱수가 아니면 그 쌍도 저장
                    divisors.add(gcdVal / i);
                }
            }
        }

        // 마지막 최대공약수는 출력해야 하므로, 1은 제외하고 gcdVal을 추가
        divisors.add(gcdVal);
        
        // 오름차순으로 정렬
        Collections.sort(divisors);

        // 결과 출력
        StringBuilder sb = new StringBuilder();
        for (int divisor : divisors) {
            sb.append(divisor).append(" ");
        }

        // 결과 출력 (끝에 공백이 나오지 않도록 처리)
        System.out.println(sb.toString().trim());
    }

    // 최대공약수 함수
    static int gcd(int a, int b) {
        while (b != 0) {
            int r = a % b;
            a = b;
            b = r;
        }
        return a;
    }
}

 

아이디어는 금방 떠올렸지만 구현을 하는 것에 있어 고생한 문제다.

 

아이디어를 같이 분석해보자.

 

숫자들을 어떤 수로 나누었을 때 나머지가 같게 하는 것이다.

즉 A = m * d + r 에서 나누는 수 d가 같을 때 r이 같아야 한다는 말이다.

그 말은 A - r = m * d가 된다는 뜻이고, 이 경우 공약수 d를 갖게된다는 말이다.

 

그 흐름을 따라가면 r이 처리하기 귀찮기 때문에 인접한 두 수를 빼준다.

예를 들어, 문제에서 제시된 6과 34를 보자.

6 = m * d + r

34 = k * d + r 이 된다. r이 복잡하니 큰 수에서 작은 수를 빼주자.

28 = d(k-m) 이 된다는 것. 이 다음인 34와 38을 동일한 방식으로 진해앟면

4 = d(x-y) 가 된다. 이런 식으로 숫자들이 나오고, 이때의 공약수 d가 존재한다면. 그게 1이 아니라면 가능하다라는 말이 된다.

 

이것을 코드로 표현한 후 이들의 약수는 전부 가능하기 때문에 추가해주면 된다.,