c언어 17425번 약수의 합 (백준)

#include <stdio.h>

int main(void) {
	long long dp[1000001] = {}; //값을 저장해 놓는 배열
	for(int i=1; i<=1000000; i++) { 
		for(int j=i; j<=1000000; j+=i) { //i를 약수로 갖는 j의 f(x)값을 증가 시킴
			dp[j] += i;
		}
        //dp[1] = f(1) = g(1) 으로 볼 수 있습니다.
        //즉 g(2) = f(2) + g(2) = f(2) + dp[1] 로 볼 수 있으며, 위의 반복문에서 f(2)는 dp[2]에 들어가 있기에, g(2) = dp[2] + dp[1] 으로 볼 수 있으며 이 g(2)값을 dp[2]에다가 넣어줍니다.
        //즉 g(3) = f(3) + f(2) + f(1) = f(3) + g(2) = f(3) + dp[2]로 볼 수있으며, 위의 반복문에서 f(3)은 dp[3]에 들어가 있기에, g(3) = dp[3] + dp[2] 으로 볼 수 있으며 이 g(3) 값을 dp[3]에다가 넣어줍니다.
		dp[i] += dp[i-1]; //dp에 들어있는 f(x)에 이전의 g(x-1)을 더해주면서 g(x) = f(x) + f(x-1) ... f(1) = f(x) + g(x-1), g(x)값을 구하게 됩니다.
	}
	
	int t;
	scanf("%d", &t);
	
	while(t--) {
		int tmp;
		scanf("%d", &tmp);
		printf("%lld\n", dp[tmp]);
	}
}

풀이 : 약수

 

1부터 1000000까지 f(x) 을 담을 배열을 만든다음

 1부터 1000000까지 증가시키면서(for(int i...) ), 자신을 약수로 갖는 수들의(for(int j=i...)) f(x) 배열에 자신을 더해줍니다.

그러면서 g(x)을 구해줍니다. g(x) = f(x) + g(x-1) 임을 이용합니다. //자세한 건 위의 코드의 주석에 있습니다.

 

이렇게 되면 1부터 1000000까지의 g(x)값이 배열에 들어가 있게 되며, 이제 O(1)로 원하는 수의 g(x)값을 출력할  수 있게 됩니다.

 

https://www.acmicpc.net/problem/17425

17425번: 약수의 합