꾸준히 개발하기

https://www.acmicpc.net/problem/2981

맞왜틀을 외치면서 풀이를 참고했다. 틀렸었다^^

일단 수학적으로 규칙을 좀 찾아야 된다. 

4개의 수를 기준으로 일단 생각해보자.

a = M * a` + r

b = M * b` + r

c = M * c` + r

d = M * d` + r

인 경우 r을 없애보면 다음과 같다.

(a-b) = M * (a`-b`)

(c-d) = M * (c`-d`)

즉 입력받는 숫자들의 차이들의 최대공약수를 구해주면 그게 바로 M이다. 

해당 M의 약수를 1 제외하고 모두 출력해주면 문제가 원하는 답이 된다.

자, 여기서^^... 약수도 그냥 출력하면 안된다. 그냥 출력하다보면 최대 입력 가능한 숫자의 범위(1,000,000,000)가 워낙 커서 시간초과가 난다. 따라서 골드바흐 문제 풀때 for문 1개로 다 처리해줬던 것처럼 다 살펴보지 말자!

예를 들어, 10의 약수는 다음과 같다 (1, 2, 5, 10) 그러면 1*10, 2*5 두 쌍으로 연산을 줄일 수 있다. 즉, 제곱근까지만 살펴본 뒤 그 수로 나눈 몫까지 함께 넣어주면 절반까지만 보면 된다!

혹시 모를 중복을 제거해주기 위해 set 자료형으로 한번 변환한 뒤, 오름차순 출력을 위해 list로 바꾼 뒤 sort하여 출력해주었다. 잊지말고 최종 숫자인 M도 출력해주자~!

코드는 다음과 같다.

import math
import sys

input = sys.stdin.readline

n = int(input())

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

gaps = []
for i in range(1, len(nums)):
    gaps.append(abs(nums[i] - nums[i - 1]))

answer = math.gcd(*gaps)

answer_list = []
i = 2

# 약수 구하는 while문 (통과)
while i <= (answer ** (1 / 2)) + 1:
    if answer % i == 0:
        answer_list.append(i)
        if i != (answer // i):
            answer_list.append(answer // i)
    i += 1

# 약수 구하는 for문 (시간초과)
# for i in range(2, int(answer ** 1/2)+1):
#     if answer % i == 0:
#         answer_list.append(i)
#         if i != (answer // i):
#             answer_list.append(answer//i)

for i in sorted(list(set(answer_list))):
    print(i, end=" ")

print(answer)

자,,, 저 코드에서 while문 for문의 차이가 뭔지 바로 보이는가..^^ 바로 거듭제곱과 나눗셈 연산자의 우선순위를 고려하지 않고 짰더니 처참하게 틀린 코드다. 나눗셈보다 거듭제곱이 연산자 우선순위가 높다...! 꼭 괄호를 생활화하자!

그리고 여러 줄을 입력받는 경우 속도가 더 빠른 sys 라이브러리를 사용하도록 코드도 바꿔보았다. 이제 input() 바로 쓰지 말고 sys.stdin.readline 기능을 활용하자

한 일주일 있다가 다시 풀어보자 잊지말고..!^^ 제목에다가 박아둬야겠다. 다시 제대로 푼 날 게시물을 수정해야겠다