코드

n = int(input())
arr = []

for _ in range(n):
    arr.append(int(input()))

# 입력을 정렬해서 받지 않으면
# 최대공약수가 음수가 나오는 경우가 발생
# 아래에서 별도로 절댓값 처리를 하지 않을 것이므로
# 그냥 편하게 처음부터 정렬을 해버리자
arr.sort()
    
# 연속하는 두 수의 차이들을 담을 리스트    
divisors = []

# 주어진 수들은 나머지 R이 모두 같으므로
# 연속하는 두 수를 빼어주는 방법을 사용하면
# 주어진 모든 수에 대하여 연립식을 세울 수 있음
# (R이 모두 소거됨)
# 이 경우, 연속하는 두 수의 차이가 M을 공약수로 가진다라는 사실을 파악
for i in range(1, n):
    divisors.append(arr[i] - arr[i-1])

# 최대 공약수 구하기
def gcd(x, y):
    while x != 0:
        y %= x
        y, x = x, y
        
    return y

# 연속한 두 수의 모든 차이에 대한
# 최대 공약수를 구할 것이므로
# 처음 두 수의 차이를 별도의 변수에 저장
_gcd = divisors[0]

# 처음 껀 따로 처리했으므로 1부터 반복 실행
for i in range(1, len(divisors)):
    _gcd = gcd(_gcd, divisors[i])

# 최종 결과를 담을 리스트    
result = []

# 1은 제외하므로 2부터 시작
# 시간 초과가 발생하므로 에라토스테네스의 체 사용
for i in range(2, int(_gcd ** 0.5) +1):
    if _gcd % i == 0:
        result.append(i)
        
        # i가 약수라면
        # i로 나눴을 때 나오는 몫 역시 약수
        # 당연한 말
        # 이를 이용하여 에라토스테네스의 체를 사용할 때,
        # 반복 횟수를 줄인 대신, 원하는 모든 약수를 담을 수 있음
        result.append(_gcd // i)

# 자기 자신은 별도로 저장
result.append(_gcd)

result = list(set(result)) # 중복이 발생할 수 있음
result.sort() # 오름차순으로 출력하라고 명시

for i in result:
    print(int(i), end=' ')

문제 해설

수학적 지식이 바탕이 되어야 풀 수 있는 문제이다. 난이도가 골드5지만 나에겐 매우 어려운 수준… 개인적으로 수리적 사고가 필요한 문제를 좋아하여 용기내어 풀어봤지만, 생각보다 많은 어려움을 느꼈다 ㅠㅠ…

각설하고!

문제를 푸는데 핵심적인 요소는 아래와 같다.

  1. 나머지가 모두 같다고 하였으므로, 주어진 수들을 연속하는 수끼리 짝을 지어 뺴주면 M이 공통된 약수라는 것을 파악할 수 있음
  2. 주어지는 숫자의 크기가 매우 클 수 있으므로, 에라토스테네스의 체 원리를 이용해야 시간 초과 방지 가능

검문

위의 식이 핵심 요소 1번의 내용이다. 이 때, M이라는 값의 모든 약수들 또한 두 수의 차이의 약수일 것이므로 M을 편의상 약수 중 최대공약수라고 생각을 하면, 최대공약수의 모든 약수들이 곧 문제에서 요구하는 정답이라는 것을 알 수 있다. (단, 문제에서 1은 제외)

이때까지의 접근을 토대로 풀이에 들어갔고, 시간 초과가 너무 뻔히 보이는 숫자 크기를 체감하여 for문을 에라토스테네스의 체 원리를 이용하여 작성했다. 이 경우, 반복의 범위가 반으로 줄었으므로, 약수를 판별할 때 i라는 숫자가 만약 약수라면, i로 나누었을 때 나오는 몫 또한 약수라는 것을 이용하여 모든 약수들을 최종 리스트에 담을 수 있었다.

수리적 접근을 요구하는 방식의 문제는 기본적인 수학 지식이 필요하여 재미는 있지만 모르면 손도 못 쓰는 경우가 있다 ㅠㅠ 많은 문제를 접하고 지식을 습득하여 더 어려운 문제도 풀 수 있는 능력을 길러야겠다!

댓글남기기

참고