[BOJ/python] 17425. 약수의 합

문제

두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다. x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)로 표현한다.

자연수 N이 주어졌을 때, g(N)을 구해보자.

 

입력

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 100,000)가 주어진다. 둘째 줄부터 테스트 케이스가 한 줄에 하나씩 주어지며 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

 

출력

각각의 테스트 케이스마다, 한 줄에 하나씩 g(N)를 출력한다.

 

 

<CODE>

import sys
ans = [0] * 1000001
tc = int(sys.stdin.readline())
for i in range(1, 1000001):
    for j in range(i, 1000001, i): #i값을 약수로 가진 인덱스들에 다 더해주기
        ans[j] += i
    ans[i] += ans[i-1] # 약수의 합이라서 앞의 값을 더해주기
for _ in range(tc):
    sys.stdout.write("{}\n".format(ans[int(sys.stdin.readline())]))

 

<REVIEW>

알고리즘 공부를 많이 해야하는 걸 요즘 느끼고 있다. 비슷한 문제인 17427번 문제를 그대로 적용했더니 시간 초과가 떴다. 그래서 여러시도를 해보다가 도저히 안되서 다른 분의 코드를 분석해보았다.

 

일단 테스트케이스 크기만큼 리스를 만들어 놓고 미리 약수의 누적합을 계산해놓는 방식으로 진행한 것으로 보인다. 위의 코드에도 적어 놓은 것처럼 이중 for문으로 i값을 약수로 가진 인덱스들을 다 더해주는 것 같다. 2번째 for문이 끝나면 앞의 인덱스 값을 더해줌으로써 누적값을 계산해주었다. 그리고 테스트케이스에 맞는 값을 차례대로 출력한 코드이다.

 

이렇게 적어놓으니 생각보다 간단한 코드이지만 어떻게 이런 코드를 생각했는지 신기할 따름이다..이해하기에도 좀 오래걸렸고(역시 과정을 이해하기에는 Python tutor가 최고!!) 부지런히 문제를 풀어야겠다..!!

 

<문제 출처>

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

17425번: 약수의 합

<코드 참고 블로그>

https://home-body.tistory.com/606