문제
두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 모든 자연수 N은 1과 자기 자신(N)을 약수로 갖게 된다.
실질적 약수(actual divisor)라는 것이 있다. 자연수 N의 약수들 중에서 1과 자기 자신(N)을 제외한 약수를 실질적 약수라고 한다. 따라서 6의 실질적 약수는 2, 3이며, 13의 실질적 약수는 없다.
SOD(Sum Of Divisor)라는 함수를 정의하자. SOD(n)은 정수 n의 모든 실질적 약수의 합을 가리킨다. 따라서 SOD(6) = 5이며, SOD(13) = 0이다. 한편, CSOD(Cumulative SOD)라는 함수도 정의해 볼 수 있다. CSOD(n)은 SOD(1) + SOD(2) + … + SOD(n)이라고 하자.
CSOD(n)을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 정수 n이 주어진다.
출력
첫째 줄에 CSOD(n)을 1,000,000으로 나눈 나머지를 출력한다.
**단순 접근으로 시간 초과 났던 코드**
N = int(input())
sod_cache = {}
def SOD(s):
divisor_list = []
sum_divisors = 0
#제곱근까지 범위 줄이기
for i in range(2, int(s**(1/2))+1):
if s % i == 0:
divisor_list.append(i)
if i**2 != s:
divisor_list.append(s // i)
if divisor_list:
sum_divisors = sum(divisor_list)
sod_cache[s] = sum_divisors
return sum_divisors
def CSOD(num):
sum_c = 0
for i in range(1,num+1):
sum_c += SOD(i)
return sum_c
print(CSOD(N) % 1000000)
진짜 쉽다고 생각해서 접근했는데 시간초과 지옥에 걸림..😱
시간 초과 해결법
1~n 까지의 정수들 중에서 1~n의 약수를 가지는 것의 개수
ex) n = 16일때 1을 약수로 가진 것의 개수 16
2를 약수로 가진것의 개수 8
3을 약수로 가진것의 개수 5
.....
이렇게 가다보면 결국 i를 약수로 가진 것의 개수는 n//i
참고 자료
https://velog.io/@yeseul/%EB%B0%B1%EC%A4%80-2247-%EC%8B%A4%EC%A7%88%EC%A0%81-%EC%95%BD%EC%88%98
