백준 2981 - 검문

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

2981번: 검문

생각없이 풀면 쉽게 답이 나오는데 시간초과가 나온다.

그래서 구글링해서 풀음;;

 

<문제 요약>

주어진 숫자들을 나누어서 공통된 나머지가 나오는 수들을 구하는 문제

그렇다해서 반복문돌리면 시간초과나옴 ㅡㅡ

 

<답>

반복문을 사용하지 않고 구해야한다.

수학적으로 접근해보자.

나눠지는 수 = (몫*나누는 수) + 1     ex) 13 = 6*2 +1

 

이를 이용하여 만약 A, B, C 라는 수를 입력받았을 경우, 세 수의 나머지가 같다면 다음과 같이 나타낼 수 있다.

A = (a*M)+R

B = (b*M)+R

C = (c*M)+R

여기서 a, b, c는 몫이며, M은 문제에서 구하고자 하는 나누는 수, R은 나머지이다.

 

이 3가지 식을 요리조리 돌려보면..

일단 나머지R을 구할 방법이 없으니 깔끔하게 식에서 정리해주도록하자.

B-A = (b-a)*M

C-A = (c-a)*M

C-B = (c-b)*M

우리가 구해야될 것은 M이다.

처음에 주어진 수가 A, B, C이므로 B-A, C-A, C-B은 구할 수 있다.

그럼 몫이 안주어졌는데 M을 어떻게 구할까? ==> B-A, C-A, C-B를 이용하자.

 

B-A, C-A, C-B은 M의 배수이며, M은 B-A, C-A, C-B의 약수이다.

올 수 있는 M을 모두 구해야하므로, B-A, C-A, C-B의 최대공약수를 구한 후, M의 약수들을 구하면 된다.

 

최대공약수를 구하는 방법 ==> 외울 것

M1) 재귀

def gcd(x, y):
    if x%y==0:
        return y
    else:
        return gcd(y, x%y)

 

M2) 유클리드 호제법

def gcd(a, b):
  a, b = max(a, b), min(a, b)
  while b != 0:
    a, b = b, a % b
  return a

 

전체 정답 코드

import sys
import math

def gcd(x, y):
    if x % y == 0:
        return y
    else:
        return gcd(y, x % y)

n = int(input())
nums = []
for i in range(n):
    nums.append(int(sys.stdin.readline()))
nums.sort()

diff = []
for i in range(1, n):
    diff.append(nums[i] - nums[i - 1])

a = diff[0]
for i in range(1, len(diff)):
    a = gcd(a, diff[i])

result = [a]
for i in range(2, int(math.sqrt(a)) + 1):  # 제곱근까지만 탐색
    if a % i == 0:
        result.append(i)
        result.append(a // i)  # 짝꿍 넣어주기(제곱근까지만 탐색하기 때문에-)
result = list(set(result))
result.sort()
print(*result) # 리스트 내의 모든 원소 출력