1. Problem
2. Solution
- 성공 code
import math
import sys
N = int(sys.stdin.readline())
lst = list(int(sys.stdin.readline().strip()) for i in range(N))
lst2 = [lst[i + 1] - lst[i] for i in range(N - 1)]
max_num = lst2[0]
for i in range(N - 2):
max_num = math.gcd(max_num, lst2[i + 1])
result = []
for i in range(2, int(max_num ** 0.5) + 1):
if max_num % i == 0:
result.append(i)
if max_num // i != i:
result.append(max_num // i)
result.append(max_num)
result.sort()
print(*result)- 실패 code -> 시간 초과
import math
import sys
N = int(input())
lst = list(int(sys.stdin.readline().strip()) for i in range(N))
lst2 = [lst[i + 1] - lst[i] for i in range(N - 1)]
lst2.append(lst[len(lst) - 1] - lst[0])
max_num = lst2[0]
for i in range(N - 1):
max_num = math.gcd(max_num, lst2[i + 1])
result = []
for i in range(2, max_num // 2 + 1):
if max_num % i == 0:
result.append(i)
result.append(max_num)
print(*result)3. Detail
이 문제는 N개의 자연수를 각각 M으로 나누었을 때, 모두 같은 나머지를 갖게 되는 1보다 큰 M의 값을 모두 구하는 문제이다. 문제를 해결할 수 있는 point는 3가지가 있다.
<3가지 중요 Point>
Point1 - 나머지가 모두 같다는 점을 활용(뺼셈으로 나머지를 0으로 만듬)
Point2 - 유클리드 호제법을 이용하여 최대공약수 구하기
Point3 - 효율적으로 약수 구하기(시간 초과 방지)위의 3가지 point들을 고려하며 살펴보자.
<example>
lst = [6, 34, 38]을 각각 M으로 나누었을 떄 모두 같은 나머지를 가져야함
lst[1] - lst[0] = 28 = (Mb + r) - (Ma + r) = M(b - a)
lst[2] - lst[1] = 4 = (Mc + r) - (Mb + r) = M(c - b)
-> lst2 = [28, 4]이를 python code로 작성하면 아래 code와 같다.
lst = list(int(sys.stdin.readline().strip()) for i in range(N))
lst2 = [lst[i + 1] - lst[i] for i in range(N - 1)]위와 같이 두 값의 차를 이용하면 나머지가 0인 값으로 만들 수 있고, 여기서 유클리드 호제법을 이용하여 lst2 list에 들어있는 값들의 최대공약수를 구한다.
max_num = lst2[0]
for i in range(N - 2):
max_num = math.gcd(max_num, lst2[i + 1])위의 code는 point2의 부분이고, lst2의 길이는 lst의 길이보다 무조건 1이 작고, 예를 들어 lst2의 길이가 2인 경우에는 list 내에 있는 값 2개씩 최대공약수를 구해야하므로 연산 횟수는 1이 되기 때문에 반복되어야하는 for문의 횟수를 N - 2로 설정한다. 그 후 반복적으로 2개의 값을 이용하여 math.gcd()로 최대공약수를 구해준다. For문이 모두 돌아가면 lst2 내의 모든 값들의 최대공약수가 계산된다.
아래 code는 point3의 효율적으로 최대공약수의 약수를 구하는 부분이다.
result = []
for i in range(2, int(max_num ** 0.5) + 1):
if max_num % i == 0:
result.append(i)
if max_num // i != i:
result.append(max_num // i)
result.append(max_num)
result.sort()
print(*result)아래의 code는 시간초과로 인한 실패 code이다.
result = []
for i in range(2, max_num // 2 + 1):
if max_num % i == 0:
result.append(i)
result.append(max_num)
print(*result)이 code의 시간초과로 인한 실패 원인은 비효율적으로 약수를 구한 것에 있다. 가장 큰 자연수로 주어질 경우는 1,000,000,000(10억)인데 시간복잡도는 0(N)이고, 그 수의 절반 정도이니 2부터 5억까지 약 5억번을 반복해서 약수인지 아닌지를 판별해야하므로 시간초과가 나오는 것이다. 그러므로 효율적으로 약수를 구해야하기 때문에
if max_num // i != i:
result.append(max_num // i)위와 같은 조건을 달아서 max_num을 i로 나누었을 때 몫이 i가 나오는 경우는 i를 두번 추가하는 것이므로 i로 나누었을 때 몫이 i가 아닌 경우에만 i와 max_num // i를 한번에 추가를 하여 효율적으로 만든다. 이 때, max_num을 i로 나누었을 때의 나머지가 0일 때를 조건으로 한다. 예를 들어 max_num = 30을 i = 5로 나눌 때 나머지가 0이고, max_num // i는 6이 되어 i와 같지 않으므로 list에 5와 6을 한번에 추가한다는 것이다.
하지만 for문에 i 값으로 1을 포함시키지 않았기 때문에 max_num와 값이 같은 약수의 경우에는 list에 추가되지 않으므로 result.append(max_num)를 해주어 포함시킨다. 결과적으로 최대공약수의 약수 집합인 result list 내의 값들은 정렬되어있지 않으므로 result.sort()로 정렬해준 후 print(*result)(Python Asterisk)를 이용하여 result list 내의 값들을 분해한 후 각각의 값들이 한번에 한 줄에 공백을 기준으로 출력되도록 한다.
