백준 2501번[C] - 상세 풀이

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

2501번: 약수 구하기

---

배열을 이용한 코드

#include <stdio.h>

int main() {
    int n, k, j = 0;
    int num[10000] = {0,};
    
    scanf("%d %d", &n, &k);
    for(int i = 1; i <= n; i++) {
        if(n % i == 0) {
            num[j] = i;
            j++;
        }
       
    }
    
    if (k)
		printf("%d", num[k-1]);
	else
		printf("0");
    
    return 0;
}

• 풀이 : 약수들을 저장할 배열 num을 선언해두고 반복문을 돌며 약수인 값들은 배열에 저장되게 됩니다.
  약수를 비교하는건 1부터 시작하지만 배열의 인덱스는 0부터 시작하기 때문에 변수 j를 0으로 선언하고 현재 i가 약수일 경우에만 값을 저장하고 배열의 인덱스를 증가(j+1)시킵니다. 따라서 크기가 작은 순서대로 약수가 저장되기 때문에 k번째로 작은 값을 찾으려면 num[k-1]을 하여 구할 수 있습니다. 

코드2

#include <stdio.h>

int main() {
    int i, n, k, cnt = 0;
    
    
    scanf("%d %d", &n, &k);
    for(i = 1; i <= n; i++) {
        if(n %  i == 0) {
            cnt++;
        }
        if(cnt == k) {
           break; 
        }

    }
    
    if (cnt >= k)
	{
		printf("%d", i);
	}
    
    else{
        printf("0");
    }
    return 0;
}

• 풀이 :  값을 배열에 저장하는 방식이 아니라 약수일 경우 cnt를 증가시키고 찾고자 하는 k번째수와 cnt가 같을 경우의 값을 구하는 방식입니다. cnt와 k가 같다는 것은 찾고자 하는 "k번째로 작은 수"라는 의미이기 때문에 그 때의 i값을 출력하면 됩니다.