[백준 1037 파이썬] 약수 (실버5, 정수론)

알고리즘 유형 : 정수론
풀이 참고 없이 스스로 풀었나요? : O

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

소스 코드(파이썬)

import sys
input = sys.stdin.readline

N = int(input())
factor = sorted(list(map(int, input().split())))

print(factor[0] * factor[-1])

풀이 요약

1. N의 약수를 오름차순으로 나열해보면, 첫 약수와 마지막 약수, 두 번째 약속과 마지막에서 한 칸 전 수, ..., 이런 규칙으로 구한 두 수들의 곱이 원래의 수 N이 된다.

2. 진짜 약수를 오름차순으로 정렬 후, 처음과 끝 수를 곱해준다.(정렬하지않고 max와 min 함수로 구해도 된다)

배운 점, 부족했던 점

• 약수의 성질 하나를 알게 됐다. (약수를 오름차순으로 나열했을 때, 1번과 i(마지막 인덱스)번 수, 2번과 i-1번 수, ..., 를 곱하면 원래의 수 N이 된다)