[백준 2981] 검문

[BanApp]

import sys

n = int(sys.stdin.readline())

arr = []

for i in range(n):
    arr.append(int(sys.stdin.readline()))

arr.sort()
t = arr[1] - arr[0]
key = []

for i in range(2,t+1):
    if t % i == 0:
        key.append(i)

ans = []

for j in key:
    cnt = 0
    for i in range(len(arr)):
        if arr[i] % j == arr[0] % j:
            cnt = cnt + 1
    if cnt == len(arr):
        ans.append(j)
        
print(*ans)

이런 게임을 암산으로 즐기는 상근이는 분명 부업으로 쿠팡맨을 뛰는 쿠팡 개발자 일것이다.
12월말에 백준 처음 시작했을때 못풀겠어서 넘겼던 문제다.
시도했지만 실패한 문제에 있어서 골드5로 승급한 기념으로 골드5 문제를 풀어봤다.
전에도 이중반복문을 사용했는데 그때는 m의 범위를 range(1,max(arr)+1)로 넣고 돌렸다.
당연히 시간초과가 뜬다.
그래서 일단 식을 적어 봤다.
arr[0] = 6, arr[1] =34 이라고 예시를 사용하겠다.
6 = (am)+k, 34 = (bm)+k 를 만족한다. 우리가 구하고자 하는것은 m이다.
따라서 m에 대한 식으로 정리해보면 m = 28/(b-a)가 된다.
근데 m은 무조건 자연수이다. 따라서 b-a가 28의 약수가 되면 된다.
28의 약수는 1,2,4,7,14,28 이다. 따라서 우리는 m 값이 주어진 값들의 차에 존재하는 공약수 값들중에 존재한다는 사실을 알았다.
이제 m의 범위가 매우 적게 줄었다.
나의 경우에는 우선 arr[0]과 arr[1] 두개만 비교해서 key 리스트를 만들고 이 안에 우리가 찾는 m이 무조건 존재한다.
따라서 이중 반복문 안에서 key값으로 나눈 값들의 개수를 비교해 줘서 모두 나머지가 같을경우 ans에 m값을 추가해준다.
그리고 리스트 안의 값들을 출력해주면 정답!

근데 정말 간신히 통과하는 코드다. 뭔가 아이디어도 구현방식도 정해는 아닌것 같다.

1. arr[1] - arr[0], arr[2] - arr[1] 이런식으로 t값을 몇개 더 만들어서 이 친구들의 공약수를 찾아줘서 key리스트 원소의 개수를 줄이면 더 빠르게 구현이 가능할까?

2. 참고로 처음에 sort 안해줬다가 틀렸는데 위 풀이는 반드시 오름차순 정렬로 되어있어야 유효한 풀이다. 항상 문제를 잘 읽자.. 테스트 케이스가 전부 오름차순이라서 입력할때 무조건 오름차순으로 입력하는줄..

3. arr 리스트 안에 있는 모든 원소들의 차 즉 n-1개의 원소를 만든 다음에 이녀석들의 최대 공약수를 계속 구해주다 보면 마지막에 남는 최대 공약수의 공약수들중 1을 제외한 것들이 답이 되지 않을까 라는 생각도 해봅니다.. 이게 맞다면 이게 더 빠를듯...

4. 우선은 풀었다는거에 만족을 합니다..ㅎㅎ