[백준 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을 출력하시오.

예제입력

6 3

예제출력

3

정보처리기사 실기 문제에서도 나오는 '약수'문제를 백준에도 약수 관련 문제가 있지 않을까 해서

찾아보고 풀어본 문제이다.

문제를 풀기 위해서는 입력받은 N값의 약수를 담을 배열이 필요했는데

나는 약수를 구하는 함수를 만들어서 풀었기 때문에 전역변수로 배열을 만들어보았다.

또한 K번째로 작은 값을 구하기 위해서 배열의 인덱스번호에 작은 순서대로 약수를 넣기 위해

인덱스번호 표시 겸 배열 내 수의 개수를 표시하기 위해 count 전역변수를 만들었다.

코드로 보면 이렇다.

#include <stdio.h>
#include <stdlib.h>
#pragma warning (disable:4996)
 
int arr[10000];
int count = 0;
 
void get_divisor(int N)
{
    int n1 = N, i;
    for (i = 1; i <= n1; i++)
    {
        if ((n1 % i) == 0)
        {
            arr[count] = i;
            count++;
        }
        else
            continue;
    }
}
 
int main()
{
    int N, K;
    scanf("%d %d", &N, &K);
 
    get_divisor(N);
    
    if (K > count)
        printf("0\n");
    else
        printf("%d\n", arr[K - 1]);
}

문제 자체는 그리 어렵지 않은 문제지만

기본적인 해결방법을 생각해보기에 좋은 문제 같았다.

나처럼 전역변수를 선언해 문제를 풀어도 되겠지만 분명 다른 방법또한 있을 것이다.

(한가지 나에게 아쉬운 점은 요즘 C++을 배우는데 빨리 배워서 이런 문제들을 C++로 구현할 수 있어야

될텐데 아직 기초밖에 못 배웠다는 점...)