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

문제 출처

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

17425번: 약수의 합

• 약수의 합을 모두 더해서 출력하는 문제로 지난번에 푼 약수의 합2 문제와 매우 유사합니다.
• 시간제한 1초, 메모리 제한 512MB

https://y00n-lee.tistory.com/41

[백준 17427]약수의 합2 - 파이썬 풀이

자료구조

• dp
  • 타입 : 리스트
  • 저장 데이터 : 각 인덱스 숫자에 해당하는 약수들의 합을 저장합니다.
• dsum
  
  • 타입 : 리스트
  • 저장 데이터 : 각 인덱스 숫자 숫자에 해당하는 약수들의 누적합을 저장합니다.

나의 풀이

이 문제는 약수의 합 2 문제와 거의 유사하지만 T(1 ≤ T ≤ 100,000)로 테스트 케이스의 개수가 아주 많아졌습니다. 그래서 약수의 합2 문제와 거의 비슷하게 풀어서 내면 시간 초과가 뜹니다. N(1 ≤ N ≤ 1,000,000)

메모리가 512MB이므로 미리 모든 약수의 누적합을 계산해 놓는 방식으로 풀었습니다.

 

1. 테스트 케이스 t의 값을 받고 그 크기만큼 arr_t 리스트를 만듭니다.

2. arr_t에 입력을 t번 받아 저장합니다. 저장하면서 입력값 중 가장 큰 max_t의 값을 찾아 따로 저장합니다.

3. max_t까지의 약수 누적합을 계산해 dsum에 저장합니다.

4. 다시 t번 반복하면서 dsum의 값을 출력합니다.

 

이렇게 해도 파이썬 코드로 제출하면 시간 초과가 나고, pypy3로 제출하면 통과합니다.

작성한 코드

• 사용 언어 : 파이썬

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


def main():
    t = int(input())
    arr_t = [0] * t
    max_t = 0
    for i in range(t):
        arr_t[i] = int(input())
        if arr_t[i] > max_t:
            max_t = arr_t[i]
    sum_divisor(max_t)
    for i in range(t):
        tmp =arr_t[i]
        print(dsum[tmp])


def sum_divisor(max_t):
    dsum[1] = 1
    tmp_sum = dsum[1]
    for i in range(2, max_t+1):
        for j in range(1, max_t//2+1):
            if i * j > MAX:
                break
            dp[i*j] += i

        tmp_sum += dp[i]
        dsum[i] = tmp_sum


if __name__ == '__main__':
    main()

• 메모리/시간 : 144600kb / 392ms

느낀 점

저번에 푼 약수의 합2 문제와 비슷한데 시간 초과를 해결하는 게 쉽지 않았습니다.

개인적으로 알고리즘 문제 풀면서 가장 멘탈이 흔들릴 때가 시간 초과일 때 같습니다.

아무래도 저는 시간 복잡도를 계산하는 알고리즘 기초가 부족한 것 같습니다...(사실 그것만 부족한 것은 아닙니다...)

기초가 가장 어려운 나 자신.... 공부해라 공부해!!(채찍)