검문

2981번: 검문

 

 

🤔생각해보기

최소공배수를 구해야하는거 같긴한데 어떤 수의 최소 공배수를 구해야할지, 도무지 어떤 방법으로 접근해야할지 감이 안와서 여러가지 방법을 시도했지만 시간 초과나 실패가 발생했다...

타 블로그를 참고해보니 '입력값들의 차이가 일정하며 그 차이들의 최대공약수의 약수가 정답'이라는 정보를 얻고 로직을 만들어봤다.

 

성공 - PyPy3가 아니라 Python3로 제출

import math

N = int(input())
nums = sorted([int(input()) for _ in range(N)])

diff = []
for i in range(len(nums) - 1):
    diff.append(nums[i + 1] - nums[i])

gcd = math.gcd(*diff)

factor = [gcd]
for i in range(2, int(math.sqrt(gcd)) + 1):
    if gcd % i == 0:
        factor.append(i)
        factor.append(gcd // i)

factor = sorted(set(factor))

print(*factor)

 

해설

• math.gcd() 에 차이값이 담긴 diff 배열 각각의 값을 한꺼번에 담아서 최대공약수를 구한다.
• factor 배열을 만들고 gcd 를 담아놓는데, gcd의 약수를 구할 것이므로 무조건 자기자신이 포함되기 때문이다. 자연스럽게 1도 약수에서 제외된다.
• 4의 약수를 계산하면 [2, 2, 4] 가 되는데 보다시피 2가 두 번 들어가게 된다. 이 중복을 제거하기 위해 set() 으로 형변환을 해준 후 오름차순으로 정렬시킨다.
• gcd 에서 활용한 것처럼 *factor 로 출력한다.