[BAEKJOON] 2981 검문

문제 요약

• 알고리즘 분류: 유클리드 호제법
• 난이도: Gold4
• 문제내용:
  • 종이의 적힌 수에서 M으로 나누었을 때 나머지가 같은 M의 수를 모두 구하세요.
  • M은 1보다 커야 한다.
• 사이트:https://www.acmicpc.net/problem/2981

2981번: 검문

문제풀이

import sys
input = sys.stdin.readline

array = [int(input()) for _ in range(int(input()))]

min_num = min(array)
result = []

for value in range(2, min_num):
    flag = True
    r = array[0] % value
    for num in array[1:]:
        if num % value != r:
            flag = False
            break
    if flag: result.append(value)
    
print(' '.join(map(str, result)))

 위에 방식대로 문제를 풀면 O(N^2)이 나온다. 종이 적힌 수가 최대 수 1,000,000,000이라서 시간 초과가 나온다. 

그래서 유클리드 호제법을 응용한 방법을 사용하면 된다.

 유클리드 호제법을 관한 내용은 아래 사이트에 참조하면 된다.

https://jih3508.tistory.com/13

유클리드 호제법(Euclidean algorithm)

유클리드 최대공약수로 접근 방법

 최대공약수로 접근하는 방법은 종이에 적힌 수를 크기순대로 정렬해서 두 개의 수를 차이를 구해서 최대 공약수를 구한 다음 최대 공약수의 약수를 구한다. 원리는 아래 같다.

   A1, A2, A3 3개 수가 있고 공통된 수는 M,  나머지는 R이라고 하자.

• A1 = A1 / M + R
• A2 = A2 / M + R
• A3 = A3 / M + R
• A1 - A2 = A1 / M + R - A2 / M - R = (A1 -  A2) / M 
• A2 - A3 = A2 / M + R - A3 / M - R = (A2 -  A3) / M 

 위에 나머지 R을 제거하기 위해서는 두 개의 수를 제거하면 나눠서 떨어지는 수를 구하면 된다. 시간복잡도를 생각해서 모든 경우의 수를 구하는 브로드포스방법 말고 유클리드 방법으로 최대 공약수를 구해서  최대 공약수에서  약수를 구하면 된다.

1. 배열을 정렬해서 각 수 앞뒤의 차이를 구한다.
2. 최대공약수 유클리드 방법으로 구한다.
3. 최대공약수 제곱근을 구한 다음  1 제외한 약수를 구한다.

코드

Python

import sys
import math

input = sys.stdin.readline

array = sorted([int(input()) for _ in range(int(input()))])
gcd = 0
for i in range(1, len(array)):
    gcd = math.gcd(array[i] - array[i-1], gcd)

result = set()

for num in range(1, int(math.sqrt(gcd)) + 1):
    if gcd % num == 0:
        result.add(num)
        result.add(gcd // num)

result.remove(1)
result = sorted(list(result))
print(' '.join(map(str, result)))

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int size = Integer.parseInt(br.readLine());
		long[] array = new long[size];
		for(int i = 0; i < size; i++) {
			array[i] = Integer.parseInt(br.readLine());
		}
		long[] re_array = new long[size - 1];
		Arrays.sort(array);
		
		
		for(int i = 0; i < size-1; i ++) {
			re_array[i] = array[i + 1] - array[i];
		}
		
		long gcd = re_array[0];
		for(int i = 1; i < size - 1; i++) {
			gcd = GCD(re_array[i], gcd);
		}
		
		Set<Long> data = new HashSet<Long>();
		
		for(long i = 1; i <= (int) Math.sqrt((double) gcd); i ++) {
			if(gcd % i == 0) {
				data.add(i);
				data.add(gcd / i);
			}
		}
		data.remove(1l);
		Long[] result = data.toArray(new Long[0]);
		Arrays.sort(result);
		
		StringBuffer sb = new StringBuffer();
		
		Arrays.stream(result).forEach(num -> {
			sb.append(num + " ");
		});
		System.out.println(sb.toString().trim());
		br.close();

	}
	
	public static long GCD(long x, long y) {
		long r;
		while(x % y != 0){
			r = x % y;
			x = y;
			y = r;
		}
		return y;
	}
	
}