문제
두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다. x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)로 표현한다.
자연수 N이 주어졌을 때, g(N)을 구해보자.
입력
첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 100,000)가 주어진다. 둘째 줄부터 테스트 케이스가 한 줄에 하나씩 주어지며 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.
출력
각각의 테스트 케이스마다, 한 줄에 하나씩 g(N)를 출력한다.
<코드>
import sys
input = sys.stdin.read
# 입력 받기
data = input().split()
T = int(data[0])
test_cases = [int(data[i]) for i in range(1, T + 1)]
max_n = max(test_cases)
f = [0] * (max_n + 1)
g = [0] * (max_n + 1)
for i in range(1, max_n + 1):
for j in range(i, max_n + 1, i):
f[j] += i
for i in range(1, max_n + 1):
g[i] = g[i - 1] + f[i]
output = []
for n in test_cases:
output.append(g[n])
sys.stdout.write('\n'.join(map(str, output)) + '\n')
<풀이과정>
-각 수의 약수들의 합을 미리 계산해두기 위해 배열 f를 사용
예를 들어 f[6]은 6의 약수들의 합(1, 2, 3, 6)을 저장
- i가 약수로 들어가는 모든 수 j에 대해 f[j]에 i를 더해주는 방식으로 계산
ex)i=2인 경우 2,4,6,...진행되며 f[2]+=2, f[4]+=2,...
-배열 g는 각 수의 약수들의 합을 모두 더한 값을 저장
'2024 코딩테스트 스터디' 카테고리의 다른 글
[6주_1일차] 프로그래머스-나누어 떨어지는 숫자 배열(Python) (0) | 2024.07.09 |
---|---|
[5주_7일차] 백준-1978 소수(Python) (0) | 2024.07.08 |
[5주_6일차] 백준-2609 최대공약수와 최소공배수(Python) (0) | 2024.07.06 |
[5주_4일차] 백준-17427 약수의 합2(Python) (0) | 2024.07.05 |
[5주_3일차] 프로그래머스-콜라츠 추측(Python) (0) | 2024.07.04 |