[자바] 백준 2981 - 검문 (java)

목차

문제 : boj2981

 

 

필요 알고리즘

• 유클리드 호제법, 정수론
  
  • gcd를 구해서 풀 수 있는 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  N개의 숫자를 M으로 나누었을 때, 나머지가 모두 같게 되는 2이상의 M을 모두 찾는 문제이다. 이 경우, 우선 가장 큰 M만 찾으면 된다. 왜냐면 나머지 M은 가장 큰 M의 약수들을 찾아주면 되기 때문이다. 그럼 문제는 N개의 숫자를 M으로 나누었을 때 나머지가 모두 같게 되는 가장 큰 M을 찾는 문제로 바뀐다. 따라서 백준 1684와 동일한 문제인데 +@인 문제라고 보면 된다. 이게 더 쉬우므로 잘 모르겠다면 1684부터 풀고 다시 풀어보자.

 

  그럼 이제 나머지가 같게 되도록 하는 가장 큰 M을 찾아야 한다.

입력으로 받은 N1과 N2가 있다고 하자. M으로 나눈 나머지가 같다는 점을 활용해 찾아보자.

N1의 나머지 R1 = N1 - Q1 * M

N2의 나머지 R2 = N2 - Q2 * M

이라고 할 수 있다.

 

  여기서 R1== R2 여야 하므로,

N1 - Q1 * M = N2 - Q2 * M 이고 따라서

N1-N2 = (Q1-Q2)M 이다.

 

  즉, 두 수 N1과 N2를 M으로 나눈 나머지인 R1과 R2가 동일한 경우 두 수의 차 또한 M으로 나눌 수 있다. Q1-Q2가 어떤 값이 나올진 모르겠지만, 아무튼 Q1-Q2도 정수이고 M도 정수이니 그냥 어떻게든 M을 가장 크도록만 만들면 된다. 그 말인즉, N1과 N2만 있다고 하면 그냥 Q1-Q2가 1이라고 치고, M은 N1-N2 자체가 되면 된다(즉, N=2 였다면 M은 두 수의 차이를 그대로 출력하면 된다는 얘기이다). 한마디로 Q1-Q2가 어떻든 상관없다.

 

  그럼 N이 3 이상일땐 어떻게 하면 될까? 식의 수를 더 늘리면 된다.

N1-N2 = (아무튼 대충 정수)M 일꺼고, N1-N3 = (아무튼 대충 정수) M 일꺼고, N2-N3 = (아무튼 대충 정수) M 일꺼다. 즉, N1-N2와 N1-N3, N2-N3 들의 최대공약수를 그냥 M이라고 치면 된다.

 

  근데 모든쌍을 보려면 O(N^2)이 필요할꺼다. 굳이 그럴필요까진 없고, 그냥 모든 수에 대한 차이만 반영되면 되므로, 값 하나 정해두고 그걸로 나머지 N-1개 전부 빼봐도 된다. 즉, N1만 하나 정해두고 무조건 N1으로만 빼도 상관없다. 근데 음수의 나머지 처리는 상당히 곤란해지므로, 가장 작은 수 하나 구해두고 그걸로 나머지 수 전부 빼면서 그 차이들의 최대공약수만 구하면 된다. (아니면 그냥 정렬해두고 arr[i+1] - arr[i] 처럼 처리해도 상관 없다.)

 

  아무튼 이렇게 M을 구했다면, 그 약수들을 구한 후 오름차순으로 출력해주면 되는 문제이다. 약수의 경우 sqrt(M) 까지만 확인해보면 되고, 입력값의 최대치가 10억이므로 sqrt(10억)은 얼마 안되서 그냥 무지성으로 찾아줘도 된다. sqrt(M) 까지만 보면 되는 이유는 '에라토스테네스의 체 혹은 소수판정 시 제곱근 까지만 확인하면 되는 이유' 글에 있다. 좀 더 효율적으로 찾으려면 '에라토스테네스의 체를 활용한 소인수분해' 글을 참고해보자.

 

private void solution() throws Exception {
    int n = Integer.parseInt(br.readLine());
    int min = Integer.MAX_VALUE;	// 입력받으면서 최소값 찾는다.
    int[] arr = new int[n];
    for (int i = 0; i < n; i++) min = min(min, arr[i] = Integer.parseInt(br.readLine()));
    int s = 0;
    while (arr[s] == min) s++;
    int gcd = arr[s]-min;
    for (int i = ++s; i < n; i++) gcd = gcd(gcd, arr[i]-min);
	// 최소값으로 나머지 수들 전부 빼면서 그 차이들의 gcd를 구한다.

    TreeSet<Integer> res = new TreeSet<>();
    res.add(gcd);
    int limit = (int) ceil(sqrt(gcd));
    for (int i = 2; i <= limit; i++) {	// sqrt(gcd) 까지 확인하며 gcd의 약수를 찾는다.
        if (gcd%i!=0) continue;

        res.add(i);
        res.add(gcd/i);
    }

    StringBuilder sb = new StringBuilder();
    for (Integer cur : res) sb.append(cur).append(' ');	// 정렬 후 출력한다. TreeSet으로 정렬했다.
    System.out.println(sb);
}

private int gcd(int a, int b) {	// 유클리드 호제법
    if (b==0) return a;

    int r = -1;
    while (r!=0) {
        r = a%b;
        a = b;
        b = r;
    }
    return a;
}

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.TreeSet;

import static java.lang.Math.*;

public class Main {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1 << 16);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    private void solution() throws Exception {
        int n = Integer.parseInt(br.readLine());
        int min = Integer.MAX_VALUE;
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) min = min(min, arr[i] = Integer.parseInt(br.readLine()));
        int s = 0;
        while (arr[s] == min) s++;
        int gcd = arr[s]-min;
        for (int i = ++s; i < n; i++) gcd = gcd(gcd, arr[i]-min);

        TreeSet<Integer> res = new TreeSet<>();
        res.add(gcd);
        int limit = (int) ceil(sqrt(gcd));
        for (int i = 2; i <= limit; i++) {
            if (gcd%i!=0) continue;

            res.add(i);
            res.add(gcd/i);
        }

        StringBuilder sb = new StringBuilder();
        for (Integer cur : res) sb.append(cur).append(' ');
        System.out.println(sb);
    }

    private int gcd(int a, int b) {
        if (b==0) return a;
        
        int r = -1;
        while (r!=0) {
            r = a%b;
            a = b;
            b = r;
        }
        return a;
    }
}