[백준/17425/파이썬] 약수의 합

---

소스코드

import sys

MAX = 1000000

dp = [0] * (MAX + 1)

s = [0] * (MAX + 1)

for i in range(1, MAX + 1):     #1부터 최대값까지

    j = 1                                   # i에 곱할 j를 선언

    while i * j <= MAX:             # i * j 값이 최대값이 넘지 않을 때까지

                                              # dp배열의 인덱스인 i의 배수에 i 값을 더해준다. 

        dp[i * j] += i                    #예를들면 3*j의 해당하는 값들은 3을 무조건 약수로 가지기 때문에 3을 더해준다 

        j += 1   

    s[i] = s[i - 1] + dp[i]            #해당 dp[i]의 값 까지 더한 누적합을 s배열에 넣어준다.

t = int(input())         

for _ in range(t):

    a = int(sys.stdin.readline())

    sys.stdout.write(str(s[a])+"\n")

---

알고리즘

그 전 포스팅에 올라온 약수의 합 2와 똑같은 문제이다. 하지만 그대로 풀면 시간초과가 나는데

DP를 사용하여 불필요한 연산을 줄이는게 포인트였다.

시간 초과가 나와서 다른 사람들의 풀이를 참고해서 풀었는데 시간초과가 나왔다.

또 다른 블로그에서 가져왔는데도 시간 초과가 나왔다.

 PyPy3으로 쓰면 같은 코드라도 시간 초과가 나질 않았는데 왜 그런지 궁금해서 찾아봤다.

---

정리하면, PyPy3에서는 실행시, 자주 쓰이는 코드를 캐싱하는 기능이 있기 때문에 ,

즉  메모리를 조금 더 사용하여 그것들을 저장하고 있어, 실행속도를 개선할 수 있다는 것이기 때문에,

간단한 코드상에서는 Python3가 메모리, 속도 측에서 우세할 수 있는 것이고,

복잡한 코드(반복)을 사용하는 경우에서는 PyPy3가 우세하기 때문에

-> 코드 상황에 맞추어 두 구현체(PyPy3, Python3)를 적절하게 사용하는 것이 효율적이라고 할 수 있다.

https://ralp0217.tistory.com/entry/Python3-%EC%99%80-PyPy3-%EC%B0%A8%EC%9D%B4

Python3 와 PyPy3 차이