BOJ-백준 17425번 약수의 합

BOJ-백준 17425번 약수의 합

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

17425번: 약수의 합

 

 

✅ Python 정답 코드 입니다. 더보기 클릭!

import sys
input = sys.stdin.readline
nums = [0] * 1000001
t = int(input())
for i in range(1, 1000001):
  for j in range(i, 1000001, i):
    nums[j] += i
  nums[i] += nums[i-1]
for _ in range(t):
  print("{}".format(nums[int(input())]))

📌 해설

모든 g(n)에 대한 데이터를 위와 같이 list에 저장합니다. 

필요한 g(n)을 nums에서 꺼내서 출력합니다.

 

🚩주의

boj 17427 번 약수의 합2 문제에서 접근한 방법과 달라서 어려웠던 문제였습니다. 

약수의 합2 문제 처럼 짧은 시간에 시간초과되지 않도록 알고리즘을 생각해야 합니다. 

성능 향상을 위해 python3 -> pypy3으로 변경하여 제출합니다.  

 

import sys
input = sys.stdin.readline
nums = [0] * 1000001
t = int(input())

 

1. 테스트케이스(t)가 100,000개 까지 입력 될 수 있으므로 sys.stdin.readline으로 입력을 받습니다. 

2. 모든 g(n)값을 저장할 list 변수 nums를 선언합니다. 

2-1. nums 는 최댓값이 1,000,000이므로 1,000,001개 만들어 줍니다. 합산을 위해 모두 0으로 초기화 합니다. 

 

for i in range(1, 1000001):
  for j in range(i, 1000001, i):
    nums[j] += i
  nums[i] += nums[i-1]
for _ in range(t):
  print("{}".format(nums[int(input())]))

3. 1~1,000,000까지 순회하는 for문을 작성합니다.

3-1. i 부터 1,000,000까지 i씩 증가하는 for 문을 작성합니다. 

3-2. j 는 i의 배수만큼 이동하면서 약수 i를 합산합니다.

3-3. 모든 num[j]를 순회하는 것이 끝나면 nums[i-1](g(n-1)) 를 nums[i]에 합산합니다. (g(i))는 합산 끝)

 

4. input에 해당하는 g(n)을 nums에서 찾아 print합니다. 

 

 

::

 

 

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