<Level 1> 약수의 합 with 파이썬

문제 설명

정수 n을 입력받아 n의 약수를 모두 더한 값을 리턴하는 함수, solution을 완성해주세요.

제한 사항

• n은 0 이상 3000이하인 정수입니다.

 

def solution(n):
    return sum([i for i in range(1, n + 1) if n % i == 0])

 

 - 제한사항이 작아서 한 줄로 처리한 문제이다.

 

 - 굳이 블로깅하지 않으려고 했으나, 제한사항이 매우 큰 경우를 생각해보기 위해서 작성하였다. 만약 제한사항이 매우 큰 숫자라면 범위를 n의 제곱근 까지로 설정하여 연산 시간을 엄청나게 단축시킬 수 있다.

 

 - 만약 28이라면 1, 2, 4, 7, 14, 28 이므로 제곱근인 5.x 까지 판단하여 (1, 28) (2, 14) (4, 7) 세 쌍을 구하고 합을 내면 된다. 즉 약수를 구하는데 기존에는 28번의 탐색을 했다면 제곱근을 사용하면 5번의 탐색만 하면 된다.

 

 

 

---

 

참고

 

코딩테스트 연습 - 약수의 합