Baekjoon17425-약수의 합

백준 사이트 17425 - 약수의 합 문제입니다.

1. 문제

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

---

2. Input , Output

---

3. 분류 및 난이도

코딩테스트 준비 - 기초 문제입니다.

---

4. 생각한 것들

• 약수를 하나씩 구하면 당연히 시간초과가 날 것이라고 생각했습니다.
• 나름 시간복잡도를 고려해서 여러가지 방법을 사용했습니다. O(nlogn)으로 줄였지만, 극한으로 더 줄여야했습니다. 결국 다른 블로그를 참조하였고 똑같은 O(nlogn)이지만 출력부분만 다른걸 봐서 출력부분에서 시간을 더 줄인것 같습니다.

---

5. code

MAX = 1000000
dp = [1] * (MAX + 1)
s = [0] * (MAX + 1)

for i in range(2, MAX + 1):
    j = 1
    while i * j <= MAX:
        dp[i * j] += i
        j+=1
for i in range(1, MAX + 1):
    s[i] = s[i-1] + dp[i]

iter = int(input())
ans = []
for k in range(iter):
    n = int(input())
    ans.append(s[n])
print('\n'.join(map(str,ans)) + '\n')

---

6. 후기

• 이게 골드4?