백준 1684번: 같은 나머지

문제: https://www.acmicpc.net/problem/1684

문제 풀이

수학

arr = n개의 수를 저장하고 정렬한 이후에 인접한 수의 차이를 인덱스 1번부터 저장하는 배열

gcd(a, b) = 두 수 a, b에 대한 최대 공약수를 구하는 함수

answer = D의 최댓값

두 수의 항등식을 변형하면 D가 두 수의 최대 공약수가 됨

그러므로 n개의 수가 있으므로 인접한 수의 차이 n - 1개에 대해 최대 공약수를 구하면 구하는 D의 최댓값이 됨

gcd(a, b)가 유클리드 호제법을 이용해 구하는 방법이므로 나머지 연산이 들어가 차이가 음수가 되면 값이 제대로 나오지 않을 수 있음

그러므로 인접한 수의 차이를 구하기 전에 n개의 수를 arr 배열에 저장하고 sort() 메소드로 정렬함

그 뒤에 배열을 재사용하기 위해 뒤에서부터 앞에 저장된 수를 빼서 차이를 저장함

arr 배열의 인덱스 1번부터 차이가 저장되므로 arr[1]부터 arr[n - 1]까지의 최대 공약수를 gcd(a, b) 함수를 이용해 구해서 answer에 저장하고 출력하면 정답

풀이 설명

정수 N을 정수 D로 나눴을 때의 몫을 Q, 나머지를 R이라고 하면 항등식 R = N - Q×D가 성립한다. 이런 항등식이 있을 때 정수 n개가 주어졌을 때 모든 수의 나머지 R이 같아지는 가장 큰 D를 구하는 문제이다.

이때 두 수가 있다고 치면 두 수는 다음과 같은 항등식을 가지게 된다. $R = N_1 - Q_1 \times D$, $R = N_2 - Q_2 \times D$ 이 두 항등식의 좌변과 우변을 서로 빼게 되면 다음과 같이 식이 변형된다.

$0 = N_1 - N_2 - (Q_1 - Q_2) \times D$ 이 식에서 $D$로 묶인 식을 좌변으로 넘기게 된다면 $(Q_1 - Q_2) \times D = N_1 - N_2$ 이 된다.

즉, 두 수를 뺀 차이가 D라는 공배수를 가지게 된다는 뜻이 되고 현재 구해야 하는 값이 D의 최댓값이 되므로 두 수의 차이의 최대 공약수를 구하는 문제로 변형이 된다.

하지만 이 문제에서는 n개의 수에 대해 D의 최댓값을 구하는 문제이므로 모든 n개의 수가 반영이 되도록 n개의 수를 나열하면 인접한 수의 차이를 모두 모아서 그 수들의 최대 공약수를 구하면 된다.

인접한 수의 차이들에 대해 최대 공약수를 구하는 방법은 유클리드 호제법을 사용하면 된다. 다만 이를 구현할 때 나머지 연산으로 구현을 하고 음수를 사용한 나머지 연산이 음수를 반환할 수 있으므로 인접한 수의 차이가 음수가 되지 않도록 n개의 수를 정렬하고 구하는 것이 좋다.

이에 따라 n개의 수를 arr 배열에 입력받고 sort() 메소드를 이용해 오름차순으로 정렬하면 된다. 그 이후에 인접한 수의 차이를 저장하기 위해 새로운 배열을 정의하기 보다 기존 배열을 재사용하기 위해 배열의 뒤에서부터 앞에 저장된 값을 빼주어 인덱스 1번부터 인접한 수의 차이가 저장되도록 만든다.

유클리드 호제법에 따라 두 수의 최대 공약수를 구하는 gcd(a, b) 함수를 정의하고 n - 1개의 차이에 대해 최대 공약수를 저장하기 위한 변수를 answer로 저장한다. 그러면 이 answer에 저장된 값이 구하는 D의 최댓값이 되므로 출력하면 정답이 된다.

소스 코드

import java.io.StreamTokenizer

fun main() = StreamTokenizer(System.`in`.bufferedReader()).run {
    fun nextInt(): Int{
        nextToken()
        return nval.toInt()
    }
    val n = nextInt()
    val arr = IntArray(n){nextInt()}
    arr.sort()
    for(i in n - 1 downTo 1){
        arr[i] -= arr[i - 1]
    }
    fun gcd(a: Int, b: Int): Int{
        var x = maxOf(a, b)
        var y = minOf(a, b)
        var r: Int
        while (true){
            if(x == 0) return y
            if(y == 0) return x
            r = x % y
            x = y
            y = r
        }
    }
    var answer = arr[1]
    for(i in 2 until n){
        answer = gcd(answer, arr[i])
    }
    println(answer)
}