처음에는 brute force 방식으로 풀었다가, 시간초과로 틀렸다.
그래서 원리를 찾아서, 배수활용하는 방식과 dynamic programming 을 활용해서 답리스트를 만들어두고 필요한 코드만 가져오는 식으로 만들었다.
틀린코드1)
dp = [0] * (1000001)
# 미리 다 리스트로 만들어두기
for i in range(1, 1000001): # 전체 돌기
for j in range(i, 1000001, i): # 약수인 곳에 다 더하기
dp[j] += i
dp[i] += dp[i-1]
cnt = int(input())
# 입력받자마자 찾아서 출력하기
for i in range(cnt):
n = int(input())
print(dp[n])틀린코드2)
변경사항
(1) f(x) 를 저장해놓는 리스트와 g(x)를 저장하는 리스트를 따로만들어서
f(x)리스트를 완성한 뒤에, g(x) 리스트를 완성하는 식으로 바꾸어보았다.
(2) 어차피 1은 모든 수의 약수이니, 처음 만들 때부터 f(x) 리스트를 1로 채웠다.
dp = [1] * 1000001
sum = [0] * 1000001
# 미리 다 리스트로 만들어두기
for i in range(2, 1000001): # 전체 돌기
for j in range(i, 1000001, i): # 약수인 곳에 다 더하기
dp[j] += i
for i in range(1, 1000001):
sum[i] = sum[i-1] + dp[i]
cnt = int(input())
# 입력받자마자 찾아서 출력하기
for i in range(cnt):
n = int(input())
print(sum[n])틀린코드3)
변경사항
for문을 while문으로 변경해보았다.
dp = [1] * 1000001
sum = [0] * 1000001
# 미리 다 리스트로 만들어두기
for i in range(2, 1000001): # 전체 돌기
j = 1
while i*j <= 1000000: # 약수인 곳에 다 더하기
dp[j] += i
j += 1
for i in range(1, 1000001):
sum[i] = sum[i-1] + dp[i]
cnt = int(input())
# 입력받자마자 찾아서 출력하기
for i in range(cnt):
n = int(input())
print(sum[n])허어......
계속 안 되는 이유를 모르겠다.
나중에 다시 풀어보러 오겠음...
