728x90
반응형
※ 문제링크
※ 관련 개념
해당문제는 나머지정리와 유클리드 호제법을 사용해서 풀어야하는 문제였다. 처음에는 단순히 브루스포트방식으로도 풀 수 있지 않을까 해서 해당 방식으로 풀어봤는데 역시나 시간초과가 나왔다. 그 후에는 나머지 정리와 DFS방식으로 변환하여 풀었더니 통과가 가능한 것으로 확인하였다. 문제풀이를 위해서는 나머지 정리와 유클리드 호제법에 대한 이해가 필요하며, 이 문제에서 사용한 방법은 아래와 같다.
1. m으로 나누었을 때 나머지 n이 모두 같다고 가정하고, 나머지 정리를 사용하면 xn = myn + n이 됨.
2. x0 = my0 + n과 xn = myn + n을 도출가능하며, 이 식을 연립하여 정리하면, (xn - x0) = m(yn - y0)의 식이 성립함.
3. 즉, 두 수의 차이를 구하고 해당 수의 약수를 구하면 문제에서 원하는 답을 구할 수 있음.
4. 두 수 차이의 조합을 구하기 위해 DFS와 백트래킹을 통해 두 수의 차이 조합을 구하고, 중복제거 진행.
5. 중복을 제거한 후에는 하나 하나씩 나눠보면서 해당 수의 약수를 순서대로 구하고 출력.
6. 약수를 구할때는 시간 절약을 위해 제곱근까지만 반복문을 걸고 나머지는 계산으로 구한 후 중복제거 및 정렬.
위의 개념을 이용하여 풀어본 코드는 아래와 같다.
import sys
input = sys.stdin.readline
N = int(input())
number_list = [int(input()) for _ in range(N)]
check_list = [False] * N
arr = []
r_list = []
def dfs(start): # dfs를 활용하여 두개의 숫자조합 및 가능한 차이값 추출
if len(arr) == 2:
r_list.append(abs(arr[0]-arr[1]))
return
for i in range(start, N):
if check_list[i]:
continue
arr.append(number_list[i])
check_list[i] = True
dfs(i)
arr.pop()
check_list[i] = False
dfs(0)
r_list = list(set(r_list)) # 차이값 중 중복되는 값들 제거
result = r_list[0]
def euclid(num1, num2): # 큰 수, 작은 수 순으로 입력
num3 = num1 % num2
if num3 == 0:
return num2
else:
result = euclid(num2, num3)
return result
for i in range(1, len(r_list)): # 유클리드 호제법을 활용하여 최대공약수 추출
if result > r_list[i]:
result = euclid(result, r_list[i])
else:
result = euclid(r_list[i], result)
answer = []
for check in range(2, int(result**(1/2) + 1)):
if result % check == 0:
answer.append(check)
answer.append(result // check)
answer.append(result)
answer = list(set(answer))
answer.sort()
print(*answer)
P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.
728x90
반응형
'알고리즘 > BOJ' 카테고리의 다른 글
[BOJ] 11051번 이항 계수2 / 사용언어 : 파이썬(python) (0) | 2021.12.21 |
---|---|
[BOJ] 3036번 링 / 사용언어 : 파이썬(python) (0) | 2021.12.21 |
[BOJ] 2609번 최대공약수와 최소공배수 / 사용언어 : 파이썬(python) (0) | 2021.12.19 |
[BOJ] 14889번 스타트와 링크 / 사용언어 : 파이썬(python) (0) | 2021.12.19 |
[BOJ] 1037번 약수 / 사용언어 : 파이썬(python) (0) | 2021.12.19 |
댓글