[백준] 2981번: 검문

이번 문제는 스도쿠 문제를 풀다 계속 틀린 이유를 못 찾겠어서 힘들어하다가 좀 쉬운 걸 풀면 자신감이 생기지 않을까 하고 풀기시작했다. 근데 이것도 틀려서 기분이 안 좋았었다 ㅡㅡ

처음에는 문제에 표면적으로 써있는 나머지가 같은 수를 2부터 하나하나 찾아주었다. 매우 쉽게 답을 얻을 수 있었다. 나는 아직 쉽게 풀리면 불길하다. 그리고 그 불길함은 시간초과를 주었다.

시간초과가 난 코드다.

N = int(input())
arr = []
for _ in range(N):
	arr.append(int(input()))
arr.sort()
for i in range(2, arr[len(arr)//2]+1):
	isSol = True
	r = arr[0]%i
	for num in arr[1:]:
		if r != (num%i):
			isSol = False
			break
	if isSol:
		print(i, end=' ')

우선 다른 블로그를 보고 유클리드 알고리즘을 쓴다는 걸 참고하고 그럼 최대공약수를 구해서 풀 수 있는 문제라는 것에서 다시 방법을 고민했다. 근데 어떤 수들의 최대공약수가 우리가 구하고자하는 나머지가 같은 수를 구하는데 이용될지를 얻기가 쉽지 않았다. 수학적으로 접근을 했었어야했는데 그러기까지 시간이 좀 걸렸다.

내 의식의 흐름을 정리해보자면,

arr[0] % M = arr[0] - arr[0] // M * M
...
arr[i] % M  = arr[i] - arr[i] // M * M
arr[i+1] % M = arr[i+1] - arr[i+1] // M * M
...
arr[N-1] % M = arr[N-1] - arr[N-1] // M * M
이라고 쓸 수 있음

근데 모든 1<= i <= N-1 에 대하여
arr[i] % M = arr[i+1] % M 이므로

arr[i] - arr[i] // M * M = arr[i+1] - arr[i+1] // M * M

arr[i+1] - arr[i] = arr[i+1] // M * M - arr[i] // M * M
= M*(arr[i+1] // M - arr[i] // M)
= M*k (k는 자연수)

따라서 연속하는 두 수의 차는 항상 M의 배수

모든 M을 구한다는 말은 즉~ 연속하는 두 수의 차들의 공약수를 전부 구하면 된다는 말이었다.

공약수는 최대공약수의 약수니까 🤖 gcd를 구하고 그것의 약수를 출력해주면 끝~ (1은 제외하고)

정답 코드

import sys
input = sys.stdin.readline

def getGcd(a, b):
	r = a % b
	while r != 0:
		a = b
		b = r
		r = a % b
	return b
	
N = int(input())

arr = []
for _ in range(N):
	arr.append(int(input()))
arr.sort() # 정렬을 안해주면 차이가 음수가 나올 수 있어서 getGcd에서 타입에러가 난다

gcd = arr[1] - arr[0]
for i in range(2, N):
	gcd = getGcd(gcd, arr[i]-arr[i-1])
	
sol = [gcd]
for i in range(2, int(gcd**0.5)+1):
# 절반까지만 검사, 제곱근이 아닐 경우 나누어 떨어지면 그 짝을 sol의 첫번째 원소로 집어넣고 마지막에 sol 출력
	if gcd % i == 0:
		print(i, end=' ')
		if i != gcd//i:
			sol.insert(0, gcd//i)
for num in sol:
	print(num, end=' ')

---

아 .. 아...ㅇ ㅏ... ㅎㅎㅎ ㅎ..... 정수론도 다시 공부를 해야겠구나