[Python] BOJ(백준) 2981번 - 검문

링크

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

2981번: 검문

난이도(solved.ac 참고)

골드5

풀이

리스트로 주어진 값들에 대해 1부터 돌면서 (현재값 - 이전값)을 절댓값 처리한 값을 넣는다. 그리고 이 값들의 최소공약수를 구한다. 그 다음 이 최소공약수의 약수를 전부 출력하면 된다. 왜냐면 최대공약수로 나눴을 때 나머지가 같다는 것은 결국 최대공약수의 약수로 나눴을 때도 나머지가 같다는 뜻이기 때문이다.

 

이 문제는 두 가지 이유로 어려웠다.

1) 아이디어 생각

  - 이정도 난이도의 수학 분야 문제가 그렇듯 아이디어를 잘 생각해내야 한다. 무슨 문제든 결국 아이디어 생각이 중요하겠지만..

2) 약수 구하기

  - 이 문제는 n의 범위가 10억까지에 해당하기 때문에 일반적인 방식으로 약수를 구하면 시간초과가 뜬다.

a = 1000000000 # 10억
for i in range(1, a):
	if a % i == 0:
    	print(i)

이 약수 구하기의 시간 복잡도는 O(N)이다. 복잡도 상으로는 무리가 없어 보이지만, a가 매우 큰 수(10억)일 경우 결국 10억번 돌아야 된다는 뜻이다. 당연히 시간초과가 뜰 것이다.

그래서 풀이에 작성한 코드대로 i와 target을 i로 나눈 몫을 모두 넣어주면 시간 복잡도를 절반으로 줄일 수 있다.

예를 들면 30이라고 했을 때 2는 30의 약수이고, 2 * 15 는 30이다. 여기서 15까지 i를 돌다가 넣어주는 것보다 2가 들어갈 경우 30을 2로 나눈 몫인 15도 같이 넣어주는 것이다. 즉 한번에 2개의 약수를 넣어주는 것. 이런 식으로 시간 복잡도를 줄여줘야지만 문제를 통과할 수 있었다.