2981번 검문

문제링크 : www.acmicpc.net/problem/2981

2981번: 검문

방법1. for문을 이용하여 입력받은 수들의 나머지가 같은 M찾기 => 시간초과

import sys
T = int(sys.stdin.readline())
numbers = [0 for _ in range(T)]
max = 0
for i in range(0,T):
    N = int(sys.stdin.readline())
    numbers[i] = N
    if(N>max) : max = N

for i in range(2,max+1):
    flag = False
    rest = numbers[0]%i
    for j in range(1,T):
        if((numbers[j]%i)==rest):
            flag = True
        else:
            flag = False
            break
    if(flag==True):
        print(i, end=' ')

방법2. 두 수의 차의 최대공약수를 구하는 방식을 반복해 배열처음~끝까지의 두수의 차의 최대공약수 구하기

  1) 주어진 수들을 오름차순으로 정렬

  2) 앞에서부터 두수의 차의 최대공약수 구하기 반복

  3) 그렇게 구해진 최종 최대공약수의 약수 구하기

def gcd(a,b):
    while(b!=0):
        a,b= b,a%b
    return a

import sys
T = int(sys.stdin.readline())
numbers = []

for i in range(T):
    numbers.append(int(sys.stdin.readline()))
numbers.sort()

common = numbers[1]-numbers[0]
for i in range(1,T):
    common = gcd(common,numbers[i]-numbers[i-1])

commonList=[common]
for i in range(2,int((common**0.5)+1)):
    if(common%i==0):
        print(i,end=' ')
        if(i!=common//i):
            commonList.insert(0,common//i)
for num in commonList:
    print(num,end = ' ')

사실 약수를 구하는 과정에서 시간 초과가 굉장히 많이 나서 여러 블로그를 보고 많이 참고했다. 단순히 while문으로 하나씩 커져가며 나머지가 0이 되는 숫자를 구하면 너무 시간이 오래걸린다. 그래서 하나의 수의 가장 큰 약수는(자기 자신 제외) 자신의 1/2인 숫자라는 점을 응용하여 구했다. 

 

+) 수학적 증명 참고 : velog.io/@kyy00n/%EB%B0%B1%EC%A4%80-2981%EB%B2%88-%EA%B2%80%EB%AC%B8

[백준] 2981번: 검문