[Python] 백준 2981번:검문 / 문제 풀이, 설명

[Python] 백준 2981번:검문 / 문제 풀이

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

2981번: 검문

 

---

º 코드

import math

times = int(input())
num = []
val = []
gcd = 0

for i in range(times):
    num.append(int(input()))
    if i == 1 :
        gcd = abs(num[1]-num[0])
    gcd = math.gcd(abs(num[i]-num[i-1]),gcd)

for i in range(2,int(gcd**0.5)+1):
    if (gcd%i)==0:
        val.append(i)
        val.append(gcd//i)

val.append(gcd)
val = list(set(val))
val.sort()


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

 

º 풀이

1. 전체적인 코드 풀이

• 나머지가 모두 같게 되는 M을 구해라. 결국 주어진 수의 공약수를 구하란 것이다. 공약수를 모두 구할 때는 최대공약수를 구해서 그 수의 약수를 구하면 된다. A라는 수는 " A = M * a + 나머지 " 라고 생각할 수 있다. B도 그렇고 그러면 A,B에는 공통된 M, 나머지가 존재한다. 
• A - B = M * (a-b) 라고 생각할 수 있다. 그러면 (a-b)는 A-B의 약수가 된다. 6,34,38이 주어졌을 때 생각하면 34 - 6 =28 이 때 gcd를 28이라 하고, 38-34 했을 때 4가 나온다. 4와 gcd의 gcd는 4가 된다. 즉 전체 수에 대한 최대공약수가 구해졌다.  
• 결국 나머지가 모두 같게 되는 M은 4의 약수가 된다. 

2.  최대공약수 찾기

for i in range(times):
    num.append(int(input()))
    if i == 1 :
        gcd = abs(num[1]-num[0])
    gcd = math.gcd(abs(num[i]-num[i-1]),gcd)

• 수가 2개 주어졌을 때 gcd를 구하고 그 뒤에 계속 gcd를 구해서 전체 수에 대한 gcd를 구할 수 있다.

3. gcd의 약수 찾기

for i in range(2,int(gcd**0.5)+1):
    if (gcd%i)==0:
        val.append(i)
        val.append(gcd//i)

• 모두가 알다시피 약수는 대칭이기 때문에 제곱근까지 구하고 (gcd//i)와 같은 형태로 대칭적으로 구해준다.

4. 출력

val.append(gcd)
val = list(set(val))
val.sort()


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

• 우리가 찾은 것은 gcd의 약수이기 때문에 gcd는 val 리스트에 들어가 있지 않다. 그래서 추가하고 중복되는 수를 제거하고, 크기순으로 정렬 후 출력해준다.

 

---

º 도움이 된 사이트

https://pacific-ocean.tistory.com/224

[백준] 2981번(python 파이썬)