JUNGOL 실력키우기 수학1 - 약수와 배수 | 약수 구하기 | 약수

기초 다지기에서 배운 내용을 응용하여 문제를 해결해야 하는 실력 키우기입니다.

실력 키우기는 비슷한 문제 유형별로 묶어서 풀어보겠습니다.

 

이번 포스팅에서는 수학1의 약수 시리즈를 풀어보겠습니다.

---

1071 : 약수와 배수

 

문제의 설명에 많은 부분이 생략되었는데 다시 문제를 쓰자면 n 개의 정수가 주어지고 미지수 m이 주어질 때 해당 정수 리스트에서 m의 약수의 합과 m의 배수의 합을 출력하는 문제입니다.

 

#include <iostream>

using namespace std;

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

	int* arr = new int[n];

	for (int i = 0; i < n; ++i)
	{
		cin >> arr[i];
	}

	int m;
	cin >> m;

	int sumFactor{ 0 };
	int sumMultiple{ 0 };
	for (int i = 0; i < n; ++i)
	{
		if (m % arr[i] == 0)
		{
			sumFactor += arr[i];
		}
		if (arr[i] % m == 0)
		{
			sumMultiple += arr[i];
		}
	}

	cout << sumFactor << endl;
	cout << sumMultiple << endl;

	delete[] arr;
}

 

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=351&sca=2030

JUNGOL | 약수와 배수 > 문제은행

 

1402 : 약수 구하기

 

이 문제는 단순하게 k번째 약수를 출력하면 되기 때문에 약수의 개수를 체크하다가 약수의 개수가 k번째가 되면 해당 숫자를 출력하면 됩니다.

 

#include <iostream>

using namespace std;

int main(void)
{
	int n, k;

	cin >> n >> k;
	
	int factorCount{ 0 }, resultFactor{ 0 };
	for (int i = 1; i <= n; ++i)
	{
		if (n % i == 0)
		{
			factorCount++;
			if (factorCount == k)
			{
				resultFactor = i;
				break;
			}
		}
	}

	cout << resultFactor << endl;
}

 

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=678&sca=2030

JUNGOL | 약수 구하기 > 문제은행

 

2809 : 약수

 

이 문제에서 문제가 되는 것은 제한 시간입니다. 제한 시간을 맞추기 위해서 알고리즘을 최적화해야 하는데 여기에서 한 가지 힌트가 존재합니다.

 

약수는 짝이 존재한다는 것이죠!

 

예를 들면 16의 약수는 1, 2, 4, 8, 16입니다. 이것을 다시 배치하면 다음과 같습니다.

{1, 16}, {2, 8}, {4, 4}

즉, 작은 값을 구하면 이 값과 짝이 되는 큰 값을 함께 구할 수 있는 것입니다.

 

여기에서 4는 같은 값을 짝으로 가지는데 이 값은 16의 루트 값입니다.

즉, 반복하는 것은 최대 값의 루트 값 이하일 때까지만 하면 된다는 것이죠.

 

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

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

	vector<int> factorList;

	int limit = static_cast<int>(sqrt(n));
	for (int i = 1; i <= limit; ++i)
	{
		if (n % i == 0)
		{
			factorList.push_back(i);
			if (n / i != i)
			{
				factorList.push_back(n / i);
			}
		}
	}

	limit = factorList.size();
	for (int i = 0; i < limit; ++i)
	{
		for (int j = 0; j < limit - i - 1; ++j)
		{
			if (factorList[j] > factorList[j + 1])
			{
				swap(factorList[j], factorList[j + 1]);
			}
		}
	}

	for (int i = 0; i < limit; ++i)
	{
		cout << factorList[i] << ' ';
	}
	cout << endl;
}

 

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=450&sca=2030

JUNGOL | 약수 > 문제은행