[백준] 2501. 약수 구하기 : C++

https://www.acmicpc.net/problem/2501

2501번: 약수 구하기

문제

어떤 자연수 p와 q가 있을 때, 만일 p를 q로 나누었을 때 나머지가 0이면 q는 p의 약수이다.

6을 예로 들면

• 6 ÷ 1 = 6 … 0
• 6 ÷ 2 = 3 … 0
• 6 ÷ 3 = 2 … 0
• 6 ÷ 4 = 1 … 2
• 6 ÷ 5 = 1 … 1
• 6 ÷ 6 = 1 … 0

그래서 6의 약수는 1, 2, 3, 6, 총 네 개이다.

두 개의 자연수 N과 K가 주어졌을 때, N의 약수들 중 K번째로 작은 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 빈칸을 사이에 두고 주어진다. N은 1 이상 10,000 이하이다. K는 1 이상 N 이하이다.

출력

첫째 줄에 N의 약수들 중 K번째로 작은 수를 출력한다. 만일 N의 약수의 개수가 K개보다 적어서 K번째 약수가 존재하지 않을 경우에는 0을 출력하시오.

---

풀이

많은 방법으로 풀이를 시도하였다

1. while문을 사용하여 입력받은 수를 1부터 차례로 나눈 후 나머지가 0인 값을 vector에 넣고 vector에서 K번째 값을 출력하도록 하였다 => 실패

2. 혹시 vector내에 너무 큰 수가 들어와서 시간 초과가 나는가 싶어 N/2로 while범위를 줄이고 나머지가 0이되는 나누는 값과 나눠진 값을 vector에 넣은 후 다시 vector을 오름차순으로 정렬하여 k번째값 출력 => 실패 (너무 복잡)

3. while문을 돌며 나머지 값이 0이 되면 K--를 해줘서 반복문이 최대한 안돌도록 하고 k가 0인 순간 num을 출력 => 실패

4. 마지막으로 while문을 for 문으로 변경 => 성공

사실 성공 했지만 왜 성공했는지 모르겠다 왜 while은 안되는건데! 이유라도 알았으면 몰라... 혹시 처리 안된 예외가 있나 한참 살핀 시간이 아깝다.

코드

#include<iostream>
using namespace std;

int main()
{
	int N, K;
	cin >> N >> K;
	int num = 1;

	for (int i = 0; i < N ;i++)
	{
		if (N % num == 0)
		{
			K--;
		}
		if (K == 0) break;
		num++;
	}
	if (K > 0)
	{
		cout << '0';
	}
	else
	{
		cout << num;
	}
	
}