[백준] 2501번: 약수 구하기 | C++ 풀이

# 문제

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

 

 

---

 

# 풀이

vector를 알고 있다면 풀이가 더 쉬웠을 것 같다.

어렵지는 않은 문제니 바로 정답 소스코드를 확인해보자.

 

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

int main(){
    vector<int> factor;
    int cnt = 0;
    int n, k;
    cin >> n >> k;

    for(int i=1; i<n+1; i++){
        if(n%i == 0){
            factor.push_back(i);
            cnt++;
        }
    }

    if(cnt < k) cout << '0';
    else cout << factor[k-1];

    return 0;
}

우선 우리는 입력되는 n의 약수의 개수를 모른다. 따라서 동적으로 크기 조정이 가능한 vector를 사용해 약수를 담을 공간을 만들어주었다.

 

또한 k번째로 작은 약수를 출력하기 전 약수의 개수와 k를 비교해야 하기 때문에 cnt 변수를 만들었다. for문을 돌며 i가 약수일 경우 factor 벡터의 끝에 i를 추가해주고, 개수도 함께 세어주기!

그 후엔 n의 약수의 개수인 cnt가 k보다 작아서 k번째 약수가 존재하지 않을 때는 0을 출력해주고,

아니라면 k번째 약수를 출력해주면 된다. 이때 vector의 인덱스가 0부터 시작하므로 k-1을 인덱스로 주어야 찾는 값을 정확하게 구할 수 있다.

 

 

 

 

 

---

 

 

2501번: 약수 구하기