[Python] 백준 파이썬 2981 검문

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

2981번: 검문

• 처음 풀이(틀림)

# 백준 2981 검문

n = int(input())

n_list = []
for _ in range(n):
  n_list.append(int(input()))

m_list = []

m = min(n_list)

for _ in range(m-1):
  n_list_copy = n_list.copy()
  
  for j in range(len(n_list)):
    n_list_copy[j] = n_list[j] % m
    
  error = 0
  for k in range(len(n_list_copy)-1):
    if n_list_copy[k] - n_list_copy[k+1] != 0:
      error += 1
      break
      
  if error == 0:
    m_list.append(m)
    
  m -= 1

for i in m_list:
  print(i, end=' ')

처음에는 문제풀 때 아이디어

1. 주어진 수 중에서 제일 작은 수로 모두 나눠줌
2. 나눈 각각의 나머지를 따로 리스트에 저장
3. 나머지가 모두 같다면 나머지를 저장한 리스트에 있는 요소들의 차가 0이 될 것
4. 만약 0이 아니면 error 변수에 값을 더해주고 반복 종료
5. error가 0이 되는 m을 m_list에 저장
6. 출력

출력 결과는 맞게 나오는데 시간 초과로 틀리게됩니다.

 

• 두 번째 풀이

지금 나머지가 모두 같아지는 M을 찾는 문제입니다.

숫자 A, B, C가 있다고 하면 세 수는 아래와 같이 표현할 수 있습니다.

$$A = M \times A^\prime + R$$

$$B = M \times B^\prime +R$$

$$C = M \times C^\prime +R$$

이걸 정리하여 R을 없애면 

$$A - B = M \times (A^\prime - B^\prime)$$

$$B - C = M \times (B^\prime - C^\prime)$$

입니다.

 

따라서 $A-B$, $B-C$의 최대 공약수를 구하는 문제가 됩니다.

import math as m

n = int(input())

n_list = []
for _ in range(n):
  n_list.append(int(input()))

n_list.sort(reverse=True) # 차를 구할 때 음수가 되면 안되니까 내림차순으로 정렬

diff = [] # 차이를 저장할 리스트
for i in range(len(n_list)-1):
  diff.append(n_list[i] - n_list[i+1])

diff_gcd = diff[0]
for i in range(1, len(diff)):
  diff_gcd = m.gcd(diff_gcd, diff[i]) # math.gcd를 이용해 최대 공약수를 구해줌                                      

cd_list=[] # 최대 공약수의 약수를 저장할 리스트

for i in range(1, int(m.sqrt(diff_gcd))+1): # 최대 공약수의 제곱근까지만 확인해줌

  if diff_gcd % i == 0:
    cd_list.append(i)
    cd_list.append(diff_gcd // i)
    
cd_list.remove(1) # 1은 필요가 없다고 문제에서 말해줬으니 삭제

cd_list = list(set(cd_list)) # 중복치가 있을 수 있으니 제거

cd_list.sort() # 출력을 오름차순으로 하라 했으니 정렬

for i in cd_list:
  print(i, end=' ') # 공백을 기준으로 출력