2981 - 파이썬

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

2981번: 검문

 

 

정말 오래 고민했다.

결국 인터넷을 보고 해답을 찾았고 아직 난 멀었다..

 

내가 처음 떠올랐던 방법은 

리스트로 받은 목록중에 가장 작은 값을 범위로 하나하나 씩 다 나누면서 일일이 있나 없나를 확인했다

그 결과 시간초과가 나왔고 진짜 하루이상 고민한거 같은데 결국 모르겠어서 인터넷을 뒤져보았다.

---

import sys

import math

input = sys.stdin.readline

N = int(input())

A=sorted([int(input()) for _ in range(N)])

ret= []

temp=[]

for i in range(1,N):

     temp.append(A[i] - A[i-1])

gcd_=temp[0]

for i in range(1,len(temp)):

     gcd_=math.gcd(gcd_,temp[i])

for i in range(2,int(gcd_**0.5) +1):

     if gcd_ % i ==0:

          ret.append(i)

          ret.append(gcd_//i)

ret.append(gcd_)

for i in sorted(set(ret)):

     print(i,end='\n')

---

다른 블로그에 찾아보면 자세한 해답이 나와있겠지만 대충 방법을 말해보자면

 

R= [ 입력받은 리스트 ]

R[0]= A X M + R  

R[1]= B X M + R

R[2]= C X M + R

 

공통적으로 가진 인수는 M 과 R이다. 

 

R[0] - R[1] = (A - B) X M

R[1] - R[2] = (B - C) X M 

 

이런식으로 나타낼 수 있다.

위 식은 아래식과 같은 형태를 띄고 있는데

1 X 3 = 3

2 X 3 = 6

3 X 3 = 9... 여기서 3은 3 6 9 의 최대 공약수이다.

고로 우리는 R[0] - R[1] , R[1] - R[2]  ...이 친구들의 최대 공약수를 찾으면 M을 찾을 수 있는 것이다.

마지막으로 결과를 append할 때 for문을 끝까지 돌려서 append 할 수도 있겠지만 그렇게 되면 시간초과가 난다.

그래서 for 문을 루트까지만 돌려서 한개의 결과값을 append 하고 나머지 값은 그 친구를 나눈값을 append 하면 된다.

가령 8 = 2 X 4 로 나타낼 수 있는데 2와 곱해지는 수를 찾을때는 8 // 2 (=4) 를 하면 찾을 수 있음을 알 수 있다.