[BOJ] 2501번 약수 구하기

약수구하기 << 문제 클릭!

✅문제 설명

• 입력 : N과 K (1 <= N <= 10000, 1 <= K <= N)
• 출력
  : 첫째 줄에 N의 약수들 중 K번째로 작은 수를 출력
  : N의 약수의 개수가 K개보다 적어서 K번째 약수가 존재하지 않을 경우에는 0을 출력

❗핵심원리

• 브루트 포스 참고자료
  • brute: 무식한, force: 힘을 의미하며
  • 완전탐색 알고리즘. 즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다.
  • 이 알고리즘의 강력한 점은 예외 없이 100%의 확률로 정답만을 출력한다.
  • 선형 구조를 전체적으로 탐색하는 순차 탐색, 비선형 구조를 전체적으로 탐색하는 깊이 우선 탐색(DFS, Depth First Search)과 너비 우선 탐색(BFS, breadth first search)이 가장 기본적인 도구이다.

✅ 1부터 N까지 나누면서 약수를 하나씩 찾는다.

💻코드

#include <iostream>

using namespace std;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, K = 0;
	int count = 0;

	cin >> N >> K;

	for (int i = 1; i <= N; i++) {
		if (N % i == 0) { // 약수이면
			count++; // 개수를 count
			if (count == K) // K번째이면
			{
				cout << i; //출력 후 종료
				return 0;
			}
			if (count > K) break; // count가 K보다 크면 바로 종료 
		}
	}

	cout << 0;

}