백준 2981 검문

풀이 방법

• 못 풀어서 다른 사람의 풀이를 참고했다.
• 주어진 숫자 N을 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 찾기
• 위 내용을 식으로 나타내면 A = Ma + R, B = Mb + R, C = Mc + R 을 만족하는 M을 찾아야 함.
• R을 제거하면, A - B = M(a - b), B - C = M( b - c ) 를 만족하는 M 을 찾아야 한다. 즉, A-B와 B-C의 최대공약수의 약수를 구하면 된다.
• 각 수에 대해 순차적으로 뺀 값을 리스트에 저장
• 리스트의 모든 값에 대한 최대공약수 구하기
• 최대공약수의 약수 구하기

import sys
input = sys.stdin.readline
N = int(input())
inp_lst = []
for _ in range(N):
    inp = int(input())
    inp_lst.append(inp)

inp_lst.sort()
lst = []
res_lst = []

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

for i in range(N-1):
    lst.append(inp_lst[i+1] - inp_lst[i])

ans = lst[0]
for i in range(1, len(lst)):
    ans = gcd(ans, lst[i])

for i in range(2, int(ans ** 0.5) + 1):
    if ans % i == 0:
        res_lst.append(i)
        res_lst.append(ans // i)
res_lst.append(ans)
res_lst = list(set(res_lst))
res_lst.sort()
print(*res_lst)

• 최대공약수의 약수 구할 때, 제곱근까지만 구해야 계산 횟수 줄일 수 있음.
• 수학적으로 생각하는 것도 필요하다고 생각함.

계획 (틀림)

• 주어지는 수를 나눈 나머지 값을 해당 인덱스에 저장한다.
  • 6인 경우, [0, 0, 0, 0, 2, 1, 0]
  • 인수는 먼저 0으로 지정, 뒤에서부터 index 2까지 순회하며 0이 나올 때까지 1씩 추가된 값을 입력
• 모든 수에 대해서 위 반복
• 가장 최근 값의 길이만큼 해당 수로 채워줌
  • 6인 경우, [0, 0, 0, 0, 2, 1, 0, 6, 6, 6, ...]