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