백준 2981번[검문] :: 약수 구하기

문제

트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다.

상근이는 시간을 때우기 위해서 수학 게임을 하기로 했다.

먼저 근처에 보이는 숫자 N개를 종이에 적는다. 그 다음, 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다. M은 1보다 커야 한다.

N개의 수가 주어졌을 때, 가능한 M을 모두 찾는 프로그램을 작성하시오.

입력

첫째 줄에 종이에 적은 수의 개수 N이 주어진다. (2 ≤ N ≤ 100)

다음 줄부터 N개 줄에는 종이에 적은 수가 하나씩 주어진다. 이 수는 모두 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. 같은 수가 두 번 이상 주어지지 않는다.

항상 M이 하나 이상 존재하는 경우만 입력으로 주어진다.

출력

첫째 줄에 가능한 M을 공백으로 구분하여 모두 출력한다. 이때, M은 증가하는 순서이어야 한다.

 

 

import sys
import math
input=sys.stdin.readline

def gcd(a,b):
    if a%b==0:
        return b
    else:
        return gcd(b,a%b)

n= int(input())
res=[]
arr=[]
rearr=[]
for i in range(n):
    arr.append(int(input()))
for i in range(n):
    if i==n-1:
        rearr.append(arr[n-1]-arr[0])
    else:
        rearr.append(arr[i+1]-arr[i])    
rearr.sort()
minrearr=rearr[0]
for i in range(n):
    minrearr=gcd(minrearr,rearr[i])

for j in range(math.ceil(minrearr**0.5)):
    if minrearr%(j+1)==0:
        res.append(j+1)
        res.append(int(minrearr/(j+1)))
print(*sorted(set(res))[1:])

 

---

문제의 메인 아이디어 찾기

 

대수론에서는 집합 간의 규칙을 찾아내는 것이 중요한데 항상 대수론에서는 문제에서의 wording 이 중요하다. 이 문제의 경우에는 내가 생각한 메인 조건은

 

나머지가 모두 같게 되는 M , 항상 M이 하나 이상 존재하는 경우만 입력으로 주어진다.

 

이라는 문장이었는데 문제를 접근할때 아~ 그렇구나 하고 넘어가는 것이 아니라 이를 중심으로 풀이를 전개해나가야한다. 얼마나 많고 얼마나 큰 숫자가 주어지던간에 집합내의 모든 요소는 x+r 형식으로 이루어진다. 예제 입력 1을 예로 들면

 

6 ➡ 4 + 2 ➡ 6 + 0

34 ➡ 32 + 2 ➡ 34 + 0

38 ➡ 36 + 2 ➡ 38 + 0

 

항상 나머지가 같게 된다. 라는 조건을 사용한다. (대수론에서는 0이 key가 되는 경우가 많다.)

그럼 우리는 여기서 단순하지만 문제 해결의 아이디어를 얻을수 있다.

 

집합의 모든 요소에 나머지(미정)을 빼주고 전부에 대한 나누어 떨어지는 수를 구하면 되겠다.

 

여기서 한번 더 생각하게 되면 나누어 질 수 있는 가장 큰 수 == 최대공약수

최대공약수의 약수들로 또다시 최대공약수가 나누어 떨어지니까 최대공약수와 그의 약수의 집합이 답이겠구나 (1을 제외한)

 

예로들면 

8과 28의 최대 공약수 4 (1,2,4)

28 = 7*4 = 7*2*2

 

 

수식으로 대강 나타내면

for i range(min(집합)):
	for j range(집합):
    	j-i로의 변환
    변환집합의 최대공약수를 구한다.
    
최대공약수의 약수가 답

 

먼저 이렇게 하게 되면 무척 큰 값의 소수가 min(집합) 이 되는 경우 시간초과가 나오게 된다. 여기서는 대수론적인 사고를 가져야하는데 다시 예제 입력 1의 예시를 가져오자면 

 

6 ➡ 4 + 2 ➡ 6 + 0

34 ➡ 32 + 2 ➡ 34 + 0

38 ➡ 36 + 2 ➡ 38 + 0

 

나머지를 제한 앞에 있는 숫자들은 항상 최대공약수의 배수들로 이루어져있다. 수식으로 나타내면

 

gcd * n + R 형태로 이루어져 있다.

 

R이 메인 조건으로 나왔고 이 R을 구하라는 말은 없기 때문에 굳이 R을 끝까지 계산에 가져갈 필요도 없고 계산에 복잡하기 때문에 서로 다른 수를 빼게 되면

 

(gcd * x + R) - (gcd * y + R) = gcd * n 형태로 나오게 된다. 골치아팠던 R은 사라지고 우리가 구해야하는 gcd만 나오게 된다.

 

자 그럼 우리는 수식을 다시한번 리프레시 할 수 있게된다.

for j range(집합):
	집합[j]-집합[j+1]
    *맨 뒤와 맨 앞도 서로 빼주어 모든 요소에 R이 남지 않게 하자
for k range(R이 없는 집합)
    변환집합의 최대공약수를 구한다.
    
최대공약수의 약수가 답

 

위처럼 코드를 짜서 제출을 하게되면 결국엔 다시 시간초과가 뜨게 되는데

 

이전 문제에서는 유클리드 호제법으로 최대공약수를 구하는 방법을 배웠다.

 

https://nstgic3.tistory.com/35#최소공배수(#1934) 

[백준/python] 정수론 및 조합론 전체 풀이(14단계)

 

하지만 그건 두수에 대한 식이지 여기에 이걸 대입하려면 악수하기 처럼 전부 구하고 결과값을 구해야하나? 생각이 들지만 또 다른 스킬을 알아보자면

 

gcd의 배수로 이루어져있다는 규칙을 활용하여 이를 오름차순으로 정렬해주고 앞부분 부터 선택정렬을 하되 결과값 중 작은 값을 인수로 두고 나머지 인수에 새로운 값을 대입하는 식으로 하게된다면 집합 내에서 최대공약수를 구해낼 수 있다.

 

시간 복잡도도 O((n^2+n)/2)에서 O(n)으로 줄어들게된다.

[가장 바깥 for문의 경우(내부에서 gcd를 얼마만큼 도는지는 고려안함)]

 

이를 함수로 나타내게된다면

rearr.sort()
minrearr=rearr[0]
for i in range(n):
    minrearr=gcd(minrearr,rearr[i])

재배열 한 것을 오름차순으로 만들어놓고 초기 최소값을 재배열 함수의 가장 처음값으로 해놓고 n 만큼 반복

---

약수 구하기 [ O(n) -> O(sqrt(n)) ]

 

사실 이 문제를 풀 때 약수구하는것을 또 O(n)으로 구해버려서 시간초과가 났고 시간 초과의 원인이 메인 아이디어를 잘못 잡았나 헷갈려서 시간을 많이 소비했다.. 전에 사용했었지만 잊어버린 나를 보고 스킬 카테고리를 만들어서 포스팅 하자고 마음먹게 한 원인이기도하다.

 

약수의 정의를 살펴보면 손쉽게 이해가 가능한데 어떤 수 n 을 나누어서 나머지가 0이 되는 정수이다. 결국에는 소인수 분해을 하였을때의 인수들의 집합인데 집합중에 a가 있다고 하면 그 반대편에는 n/a 가 있어 n을 만들게 된다. 따라서 n의 제곱근 까지만 서칭을 하고 찾아진 약수를 n에서 나눈값을 또 구해주면 약수가 전부 구해지게 된다.

 

중복값이 나올 수도 있으니 set 등으로 중복을 없애주는 것을 잊지말자

 

다시 보는 최종 수식

import sys
import math
input=sys.stdin.readline

def gcd(a,b):
    if a%b==0:
        return b
    else:
        return gcd(b,a%b)

n= int(input())
res=[]
arr=[]
rearr=[]
for i in range(n):
    arr.append(int(input()))
for i in range(n):
    if i==n-1:
        rearr.append(arr[n-1]-arr[0])
    else:
        rearr.append(arr[i+1]-arr[i])    
rearr.sort()
minrearr=rearr[0]
for i in range(n):
    minrearr=gcd(minrearr,rearr[i])

for j in range(math.ceil(minrearr**0.5)):
    if minrearr%(j+1)==0:
        res.append(j+1)
        res.append(int(minrearr/(j+1)))
print(*sorted(set(res))[1:])

 

 

이 문제와 비슷한 문제들의 풀이를 보러가려면 ⬇⬇⬇

[백준/python] 정수론 및 조합론 전체 풀이(14단계)