문제:
트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다.
상근이는 시간을 때우기 위해서 수학 게임을 하기로 했다.
먼저 근처에 보이는 숫자 N개를 종이에 적는다. 그 다음, 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다. M은 1보다 커야 한다.
N개의 수가 주어졌을 때, 가능한 M을 모두 찾는 프로그램을 작성하시오.
입력:
첫째 줄에 종이에 적은 수의 개수 N이 주어진다. (2 ≤ N ≤ 100)
다음 줄부터 N개 줄에는 종이에 적은 수가 하나씩 주어진다. 이 수는 모두 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. 같은 수가 두 번 이상 주어지지 않는다.
항상 M이 하나 이상 존재하는 경우만 입력으로 주어진다.
출력:
첫째 줄에 가능한 M을 공백으로 구분하여 모두 출력한다. 이때, M은 증가하는 순서이어야 한다.
풀이방법:
N개의 숫자들을 M으로 나눴을 때 나머지가 모두 같은 M을 찾기 위해서는 N개의 숫자들을 큰 순서로 정렬한 뒤에 그들의 차를 구하고 GCD를 계산하면 된다. 이 것이 가능한 이유는 간략히 설명하면 다음과 같다.
숫자 A, B가 있고 M으로 나누면 나머지가 R로 같다고 하자. 그러면 다음과 같이 식으로 쓸 수 있다.
A = a*M + R
B = b*M + R
이들의 차를 구하면 다음과 같이 된다.
A-B = (a-b)*M
따라서 M은 A와 B의 GCD를 의미하게 되고 가능한 M은 해당 GCD들의 약수일 것이다.
python의 math.gcd를 사용하고, 이 값에 대해 약수를 구하는 함수를 구해 M을 출력하도록 한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
from math import gcd,sqrt
def divisor(n):
divList = {n}
for i in range(2,int(sqrt(n)+1)):
if n%i==0:
divList.add(i)
divList.add(n//i)
divList = sorted(list(divList))
return divList
n = int(input())
numbers=[]
for _ in range(n):
numbers.append(int(input()))
numbers.sort(reverse=True)
diff = []
for i in range(len(numbers)-1):
diff.append(numbers[i]-numbers[i-1])
answer = diff[0]
for i in range(1,len(diff)):
answer = gcd(answer,diff[i])
print(*divisor(answer))
|
cs |
문제링크:
'Algorithm > Python' 카테고리의 다른 글
| [BOJ]3273. 두 수의 합 (0) | 2021.04.27 |
|---|---|
| [BOJ]9184. 신나는 함수 실행 (0) | 2021.04.22 |
| [BOJ]10819. 차이를 최대로 (0) | 2021.02.25 |
| [BOJ]14888. 연산자 끼워넣기 (0) | 2021.02.23 |
| [BOJ]2885. 초콜릿 식사 (0) | 2021.02.16 |