약수의 합
-
[Algo Rhythm🕺💃] BOJ 17425 - 약수의 합Algo Rhythm🕺💃/BOJ 2021. 6. 24. 21:43
문제 분석 약수의 성질 중 하나는 두 자연수 $a, b$에 대하여 $a$가 $b$의 배수이면 $b$는 $a$의 약수(들) 중 하나라는 것이다. 그리고 이 문제는 자연수 $n(1 \le n \le 10^6)$을 입력할 때 $g(n)$을 출력할 것을 요구한다. 이때 $g(n)$은 아래와 같은 수식으로 정의할 수 있다. $g(n)= \begin{cases} g(n - 1) + f(n) & n \gt 1\\ 1 & n = 1 \end{cases}$ 앞서 말한 두 가지를 종합할 때 이 문제는 약수의 성질을 이용하여 모든 $n$에 대하여 $g(n)$을 구하여 저장한 다음 테스트케이스로 $n$에 속하는 자연수 $a$가 들어올 때마다 $g(a)$를 출력하는 문제로 이해할 수 있다. 문제 풀이 1. $g(n)$을 저장하..