알고리즘 문제풀이 [백준 17425]

🔎 BACKJOON 17425

• 문제

  두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다. x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)로 표현한다.
  자연수 N이 주어졌을 때, g(N)을 구해보자.

• 입력

  첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 100,000)가 주어진다. 둘째 줄부터 테스트 케이스가 한 줄에 하나씩 주어지며 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다

• 출력

  각각의 테스트 케이스마다, 한 줄에 하나씩 g(N)를 출력한다.

#include <iostream>

using namespace std;
const int MAX = 1000000;

long long ans[MAX];

int main(int argc, char const *argv[]){
	ios_base::sync_with_stdio(0);
    cin.tie(0);
	
	int m;
	
	cin >> m;
	for (int i = 1; i <= MAX; i++){
		for (int j = 1; i * j <= MAX; j++)
		{
			ans[i * j] += i;
		}
		ans[i] += ans[i - 1];
	}
	for (int i = 0; i < m; i++){
		int n;
		cin >> n;
		cout << ans[n] << "\n";
	}

	return 0;
}

이 문제는 앞서 풀이한 17427문제의 간단한 변형이지만 그대로 풀게 된다면 바로 타임에러가 뜬다..!

배열에 저장하여 배열의 인덱스로 약수의 합을 저장한 뒤 반복으로 뽑아준다..!

ios_base::sync_with_stdio(0);
cin.tie(0);  

위의 코드를 사용해야 cin, cout의 속도가 개선된다..

문제 링크

풀이 깃허브 링크