백준 2981 풀이 (검문, 유클리드 호제법, 약수 구하기)

이 문제는 정말 나의 탁월한 운빨로 풀게된 문제이다.

문제를 읽게 되면 그렇게 어려워 보이지 않는다. 읽고나서 바로 생각나는 것은 2부터 나누기 시작해서 다 나누어 떨어지면 되는거 아닌가? 하는 생각이 든다. 

나도 당연히 그렇게 풀어볼까 하다가 조금이라도 연산을 줄이고자 나머지를 기준으로 값을 나누어 보기 시작했다.

물론 잘못된 방법이었다. 바로 풀릴리가 없지ㅋㅋㅋㅋ

그래서 고민하다가 도달한 결론은 노가다로 푸는게 아니고 무언가 규칙이 있을것이란 생각이었다.

테스트 케이스로는 6,34,38을 준다. 그래서 이걸로 값을 바꿔보기도 하다가 1씩 증가시켜보았다.

7, 35, 39 

신기한것은 이렇게 1이 증가하여 전부 홀수가 되었음에도 같은 나머지를 만들기 위해서 2, 4가 필요한 것이었다. 그래서 각 값들의 차를 구해보았다.

[28, 4] 그리고 이 값의 최대 공약수가 4이다. 그래서 2,4가 필요한 것이었다. 

그러나 차가 여러개일 수 있다.

[4, 28, 32, 56] 이러한 경우 굳이 모든 값들의 최대 공약수를 구할 필요가 없다. 가장 작은 수인 4와 28의 최대 공약수만 구하면 모든 값의 최대 공약수가 된다.

 

즉, 각 값들의 차에서 최대 공약수를 구하면 이 값의 약수들이 출력에 입력되면 된다. 

그러나 여기 중요한 점은 만약 차의 값이 굉장히 큰수일 경우 약수만을 구하는데에도 상당히 많은 시간을 할애해야한다.

그래서 약수를 구하는 3가지 방법을 소개한다.

1. 1부터 n까지 전부 나누어 보며 0으로 떨어지는지 확인

2. 1부터 n//2+1까지 전부 나누어 보며 0으로 떨어지는지 확인

3. 1부터 int(n**0.5)+1까지 나누어 보며 떨어지는 값과 몫 구하기

여기서 가장 빠른 시간을 가지는 것은 3번째 방법이다. 따라서 나는 3번째 방법을 선택하여 코딩을 진행했다.

 

from math import gcd
n = int(input())
tmp = []
sub = []
for i in range(n):
    if i == 0:
        tmp.append(int(input()))
    else:
        a = int(input())
        tmp.append(a)
        sub.append(abs(tmp[i] - tmp[i-1]))

sub = list(set(sub))
sub.sort()
if len(sub) != 1:
    t = gcd(sub[0],sub[1])
else:
    t = sub[0]
yak = []
for i in range(2,int(t**0.5)+1):
    if t % i == 0:
        yak.append(i)
        if i != t//i:
            yak.append(t//i)
yak.append(t)
yak.sort()
for i in yak:
    print(i,end=' ')