[자바] 백준 1684 - 같은 나머지 (java)

목차

문제 : boj1684

 

 

필요 알고리즘

• 정수론, 유클리드 호제법
  
  • 의외로 GCD 문제이다! 

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

 

 

풀이

 우선 N이 2인 경우만 생각해보자. 문제에서 입력된 어떠한 정수 2개를 N1, N2라고 하면, R1==R2가 되려면 아래처럼 식이 전개될 것이다.

 

  따라서 N2-N1 즉, 두 수의 차이는 정수인 Q2-Q1과 D의 곱이 된다. 이 때 Q2-Q1이 뭔지는 모르겠지만 아무튼 정수인 D가 가장 크게 나오면 된다. 그럼 N=2 이라면 그냥 N2-N1 자체가 답이 된다. 예를들어 71과 5라면 71-5가 답이 된다! 둘의 나머지는 5로 동일하다.

 

  이 문제는 N이 3 이상인 경우에도 계산할 수 있어야 한다. 아무튼 근데 자바의 경우 음수에 대한 나머지 연산은 제대로 안나오므로 귀찮으니, 가장 낮은 값을 찾는다. 그 값을 다른 값에서 빼주면 항상 0이상의 값이 나오므로 나머지 연산을 별다른 처리 없이 할 수 있다.

 

결론은

1. 입력값 중 가장 낮은 값을 찾는다.

2. '1'에서 찾은 값을 입력받은 값에서 각각 전부 빼준다.

3. 해당 값들의 GCD를 찾는다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    static 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[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) arr[i] = Integer.parseInt(st.nextToken());
        Arrays.sort(arr);
        int min = arr[0];
        int i = 0;
        for (; i < n; i++) if ((arr[i]-=min) != 0) break;
        if (i == n) {
            System.out.println(min);
            return;
        }
        int gcd = arr[i++];
        for (; i < n; i++) gcd = gcd(gcd, arr[i]-=min);
        System.out.println(gcd);
    }

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