[JAVA + Python] BOJ 2981 검문

출처 : 백준

 

왜 정답 비율이 저렇게 낮은지 알법한 문제였다. 처음엔 유클리드 호제법을 알지 못한 체 무작정 최대 공약수 구하다 보니 시간 초과가 정말 괴롭게 했다..

 

수학적으로 접근하는 방법도 있지만 필자는 숫자들의 패턴을 보고 알고리즘에 접근했다. 예를 들어

 

N=2, 주어진 입력값은 [2, 12] 라고 할 때 M은 2, 5, 10이다 이를 보고 알아낸 것은 같은 M을 가지려면 두 수의 차의 약수를 구하면 되는구나라고 생각했다. 12-2 = 10이고 10의 공약수는 1을 뺀 2, 5, 10이 되기 때문이다. 

 

만약 N=3 이고  2, 12, 18 가 주어진다면 M은 2 뿐이다. 2와 12의 차이는 10이고 18과 12의 차이는 6이기 때문에 10과 6의 최대 공약수는 2이고 최대 공약수의 약수 중 1을 제외하면 2만 남는다.  

 

이 패턴을 찾아내는데 꽤 많은 시간을 쓴 것 같다. 수학적으로 접근할 줄 알았으면 훨씬 빨랐을 텐데 아쉽다..

 

a라는 숫자와 b라는 숫자가 주어지고 같은 나머지 값을 같는다고 하면 다음과 같다.

a = M*p + r

b = M*q + r

 

같은 r이기 때문에 b-a = M(q-p)이고 M은 (b-a)의 공약수이다. 앞선 예제처럼 a=2, b=12라고 하면 M 은 12-2의 약수 들이었다. 

 

문제에선 a, b 두 숫자만 주어지지 않고 여러 숫자가 주어진다. N=5 이고 a, b, c, d, e가 주어진다면

((b-a)의 약수, (c-b)의 약수, (d-c)의 약수, (e-d)의 약수) 의 약수를 구하면 된다. 즉 최대공약수를 구해 그 최대공약수의 약수를 구하면 된다.

 

(b-a)와 (c-b)의 최대공약수(g1) 를 구하고 (d-c)와 g1의 최대공약수를 구하는 과정을 이어가면서 최종 g1의 약수들을 출력하면 된다.   

 

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int[] arr = new int[N];
		for(int i=0; i<N;i++) {
			st = new StringTokenizer(br.readLine());
			arr[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arr);
		int gcd_ = arr[1]-arr[0];
		for(int i=2;i<N;i++) {
			gcd_ = gcd(gcd_, arr[i]-arr[i-1]);
		}
		for(int i=2;i<=gcd_;i++) {
			if(gcd_%i==0) bw.write(i+" ");
		}
		bw.flush();
		bw.close();
	}
	public static int gcd(int a, int b) {
		if(b==0) return a;
		return gcd(b, a%b);
	}
}

 

최대공약수는 gcd 라는 유클리드 호제법을 바탕으로 구현한 메서드를 통해서 구하고 각 입력값의 차가 음수가 되는 것을 방지하기 위해 arr을 오름차순으로 정렬해주었다. 이후 모든 케이스의 최대공약수(gcd_)를 구해 gcd_의 약수를 출력하였다.

 

 

+같은 알고리즘을 가지고 파이썬으로도 구현해보았는데 역시나,, python3는 시간 초과를 뱉고 Pypy3는 통과를 하였다.

def gcd(a,b):
    if b==0:
        return a
    return gcd(b, a%b)
N = int(input())

li = []
for i in range(N):
    li.append(int(sys.stdin.readline()))

li.sort()

gcd_ = li[1]-li[0]
for i in range(2, N):
    gcd_ = gcd(gcd_, li[i]-li[i-1])
    
for i in range(2, gcd_+1):
    if gcd_%i ==0:
        print(i, end=" ")