sm 기술 블로그
109. 2981(검문) 본문
import sys
input = sys.stdin.readline
T = int(input())
num = sorted([int(input()) for _ in range(T)])
result = set()
def GCD(x, y):
while(y != 0):
r = x % y
x = y
y = r
return x
numGCD = num[1]-num[0]
for i in range(2, T):
numGCD = GCD(numGCD, abs(num[i]-num[i-1]))
for j in range(2, int(numGCD**0.5)+1):
if(numGCD % j == 0):
result.add(j)
result.add(numGCD//j)
result.add(numGCD)
print(*sorted(list(result)))
문제요약
수가 주어졌을 때 M으로 나눌 때 나머지가 동일한 경우의 M을 구하라. (상근아... 검문이나 제대로 받아;;)
설명
최대 1,000,000,000이라는 어마어마한 숫자로 인해 시간초과가 발생할 확률이 높은 문제이다.
수의 형태는 A = B * C + R 이다.
예를들어 A가 19이면 19 = 5 * 3 + 4 이며 위의 문제 첫번째 예시인 6 , 34 , 38에 적용하면,
다음과 같다.
M으로 나누었을 때 두 값의 나머지는 동일하다는 조건으로 인해,
다음과 같은 식이 완성된다.
이때, (6-34) / M 의 M과 (34-38) / M 의 M의 M이 같다.
때문에 (6-34) 와 (34-38)의 공약수를 구하면된다. 즉, 28과 4의 최대공약수를 찾고 그 최대공약수의 약수를 구하면 된다.
이를 빠르게 두번째 입력에 적용해 보면 다음과 같다.
입력 => 5 17 23 14 83
num = sorted([int(input()) for _ in range(T)])
정렬을 통해 다음값 - 현재값을 하여 음수가 발생하지 않도록 할 것이다.
def GCD(x, y):
while(y != 0):
r = x % y
x = y
y = r
return x
유클리드 호제법을 사용하여 최대공약수를 구한다.
numGCD = num[1]-num[0]
for i in range(2, T):
numGCD = GCD(numGCD, abs(num[i]-num[i-1]))
먼저 numGCD를 만들고 (만약 TestCase가 2개이면, 그게 바로 최대공약수가 된다.) , 최대공약수를 구해간다.
예들들어
다음과 같이 진행되는 것이다.
for j in range(2, int(numGCD**0.5)+1):
if(numGCD % j == 0):
result.add(j)
result.add(numGCD//j)
result.add(numGCD)
print(*sorted(list(result)))
수가 커지면 끝까지 반복문을 돌리기에는 시간이 많이 걸린다.
때문에 제곱근 이후부터는 나눠도 의미없다는 것을 이용하여 반복 횟수를 줄인다.
예를들어 10의 제곱근은 3.16이다.
4 이후 부터는 이미 앞에서 구한 값으로 약수를 구할 수 있고, 제곱근 약수가 없다면 이후에도 약수가 없다.
위 로직을 그림으로 설명하면 다음과 같다.
만약 나누는 수가 중복이 발생할 수도 있기 때문에 집합(set)에 값을 집어넣고 리스트로 바꾼 뒤 정렬을 통해 출력을 한 것 이다.
'문제 > 백준_파이썬' 카테고리의 다른 글
111. 11050 (이항계수 1) (0) | 2022.06.26 |
---|---|
110. 3036 링 (0) | 2022.06.25 |
108. 1934(최소공배수) (0) | 2022.06.24 |
107. 2609(최대공약수와 최소공배수) (0) | 2022.06.24 |
106. 1037(약수) (0) | 2022.06.24 |