-
17425. [Python]약수의 합Python_알고리즘/Gold IV 2023. 10. 9. 18:18
1. 문제
https://www.acmicpc.net/problem/17425
17425번: 약수의 합
두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더
www.acmicpc.net
2. 접근 방법
- 시간 제한: 1초
- 메모리 제한: 512MB
- 에라토스테네스의 체
3. 파이썬 코드
import sys # 약수 구하는 함수 def divisor(): # 약수를 저장할 리스트 num_list = [1] * 1000001 # 정답을 출력할 리스트 ans = [0] * 1000001 # 2부터 1,000,000 까지 반복 for i in range(2,1000001): # i 부터 1,000,000 까지 반복 for j in range(i ,1000001,i): # 각 1씩 저장된 리스트 j 에 i 값을 더해줌 # i 값을 더하는 이유가 i 의 배수이기 때문에 num_list[j] += i # 저장된 num_list의 i 값과 ans 의 이전값을 더해나감 for i in range(1,1000001): ans[i] += ans[i-1] + num_list[i] return ans input = sys.stdin.readline answer = divisor() T = int(input()) for _ in range(T): num = int(input()) print(answer[num])
4. 문제를 풀고난 후 생각
- 문제의 메모리가 512MB사용되는 문제인 것을 보고 에라토스테네스의 체를 살짝 응용하여 문제를 해결하였다.
- 처음 문제를 보았을때는 어떤 방식으로 접근해야 하는지 많은 고민을 했었고, 질문 게시판을 찾고 다른 사람들의 코드를 살펴보고 이해한 후 해결했다.
- 1 부터 1,000,000까지 수들이 1을 가지고 있으므로 1로 저장된 리스트를 생성한 후 2부터 1,000,000 까지 반복문을 진행하며 이중 for문을 통해서 내부에 i 부터 1,000,000 까지 i 씩 증가하는 반복문을 생성한다.
- 이렇게 j 값은 i 씩 증가하는 숫자가 되며 이는 i를 포함하는 숫자들에 i 를 더해주기 때문에 i 의 배수들이 된다.
- 이렇게 2부터 1,000,000 까지 모든 배수들의 합을 리스트 인덱스로 저장해둔 후 ans 라는 정답 리스트에 그 인덱스 값 + ans에 저장된 이전 값을 해줄 경우 정답을 출력할 수 있다.
5. 문제를 푸는데 도움이 되는 지식
- 에라토스테네스의 체
'Python_알고리즘 > Gold IV' 카테고리의 다른 글
1253. [Python] 좋다 (1) 2024.03.13 1261. [Python]알고스팟 (1) 2024.03.06 1753. [Python]최단경로 (0) 2024.03.03 9019. [Python]DSLR (1) 2023.10.08 10942. [Python]팰린드롬? (1) 2023.10.07