[C++ 공부] 9. 모두의 약수

 

"it 취업을 위한 알고리즘 문제풀이 (with C, C++)  코딩테스트 대비" 강의 문제 풀이 입니다.

 

#include <iostream>

using namespace std;

int cnt[500001];

int main(void)
{
	int N;
	cin >> N;

	for (int i = 1; i <= N; i++)
	{
		for (int j = i; j <= N; j = j + i)
		{
			cnt[j]++;
		}
		
	}
	for (int i = 1; i <= N; i++)
	{
		cout << cnt[i] << ' ';
	}

	return 0;
}

++ 시간 초과 코드 (시간 복잡도 = n^2)

#include <iostream>
#include <string>

using namespace std;

int main(void)
{
	int N, count;
	cin >> N;

	for (int i = 1; i <= N; i++)
	{
		count = 0;
		for (int j = 1; j <= i; j++)
		{
			if (i % j == 0) count++;
		}
		
	}

	return 0;
}