BOJ 2501.약수 구하기

www.acmicpc.net/problem/2501

2501번: 약수 구하기

첫 번째 풀이

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;


int main(void)
{
	int N,K;
	vector<int> v;
	cin >> N >> K;
	for(int i = 1;i<=N;i++)
	{
		if(N%i==0)
		{
			v.push_back(i);
			
		}
	}
	sort(v.begin(), v.end());
	cout<<v[K-1];
	
	return 0;
}

구하고자 하는 수를 1~N 숫자 하나씩 다 나눠서 나머지가 0인것을 구하는 방법이다.

6을 1~6의 모든 숫자로 나눠서 0이 나오는 숫자는 1, 2, 3, 6이 나오게 된다.

 

두 번째 풀이

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;


int main(void)
{
	int N,K;
	vector<int> v;
	cin >> N >> K;
	for(int i = 1;i*i<=N;i++)
	{
		if(N%i==0)
		{
			v.push_back(i);
			v.push_back(N/i);
		}
	}
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(),v.end()), v.end());
	cout<<v[K-1];
	
	return 0;
}

1~6까지 숫자에서 for문 종료 조건을 i 제곱으로 바꾸었는데, 이는 나누는 수의 제곱이 N보다 작을 때까지만 검사하면 되기에 더 큰 수의 약수를 구할 때 횟수가 첫 번째 풀이보다 작은 것을 알 수가 있다.

unique는 중복 숫자를 걸러내기 위함이며, 중복 숫자는 맨 뒤로 남겨지게 된다. 남겨진 값을 erase를 통해서 지우게 해주었다.