17425

날짜 : 2022. . 

사용 언어 : python

 

문제

 

 

코드

import sys

m = 1000000
f = [0] * 1000001
g = [0] * 1000001

for i in range(1, m + 1):  # 약수
    j = 1
    while i * j <= m:
        f[i*j] += i
        j += 1

g[1] = 1
for i in range(2, m + 1):
    g[i] = f[i] + g[i - 1]

t = int(sys.stdin.readline())
for _ in range(t):
    n = int(sys.stdin.readline())
    print(g[n])

 

 

풀이

- 이전에 풀었던 문제 17427을 응용하여 풀이한 문제이다.

- 테스트케이스를 입력받고 그에따라 바로바로 연산하는 방식이 아닌, f(n)을 먼저 구하고 이를 이용해 g(n)까지 모두 구한 다음 테스트케이스와 n값을 입력받아 그 값을 차례차례 출력하는 것이 이 문제의 포인트였다.

- 그러므로 일반 for문을 통해 f값들을 구한다.

- 다만 배수의 방식으로 구하기 때문에 A = B * C라고 가정했을 때 오직 B만 A의 약수로 포함시킨다는 점을 이용해 while문을 구성한다. (B는 1부터 A까지 증가하면서 리스트 f의 인덱스에 맞게 값을 추가한다.)

- 한편 g(n) = f(n) + g(n-1) 이라는 점화식이 기존에 도출되었기 때문에 다이나믹 프로그래밍을 활용하여 리스트 g를 구한다.

- 위의 과정을 모두 마친 다음 각각 테스트케이스와 n값들을 입력받은 후 알맞은 아웃풋을 출력한다.

 

 

알게된 점

- 배수로 접근해야 한다는 점은 대충 감은 있었지만 에라토스테네스의 체를 활용해서 문제를 풀 수 있다는 것은 조금 의외였다.

 

 

참고 사이트

- https://enhjh.tistory.com/38

[백준/수학] 17425 약수의 합(Python, 파이썬)