백준 알고리즘 2501번 약수 구하기 (C언어)

브론즈Ⅲ

 

 

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

2501번: 약수 구하기

 

풀이 방법

 

약수란 어떤 자연수를 나누어 떨어지게 하는 수이다. 즉 12의 약수는 1, 2, 3, 4, 6, 12이다.

N의 약수들 중 K번째로 작은 수를 출력하는 문제이기 때문에 for문을 이용해 N을 1부터 2, 3, 4, ... N까지 나눈 나머지를 확인한 후, 나눈 나머지가 0일 때마다 cnt를 1씩 증가시키며 k번째로 작은 수를 찾아낸다.

 

내 코드

#pragma warning(disable:4996)
#include <stdio.h>
 
int main(void) {
    
    int n, k, i, cnt = 0, flag = 0, result;
 
    scanf("%d %d", &n, &k);
 
    for (i = 1; i <= n; ++i) {
        if (n % i == 0)
            ++cnt;
        if (cnt == k) {
            flag = 1;
            break;
        }
    }
    if (flag == 1)
        result = i;
    else
        result = 0;
 
    printf("%d\n", result);
 
    return 0;
}
 

 

 

코드설명

반응형

1   | scanf 함수를 사용할 때 경고창을 띄우지 않도록 하는 전처리 지시문이다.

2   | scanf, printf 함수를 사용하기 위한 전처리 지시문이다.

6   | 각각의 변수를 다음의 용도로 정의하였다.

        // cnt : N의 약수를 찾을 때마다 1씩 증가시키며 K번째로 작은 수를 찾기 위해

        // flag : K번째 약수가 존재하는지, 존재하지 않는지를 체크하기 위해

        // result : K번째 약수 or 0을 출력하기 위해

10  | for문의 i로 단순한 횟수를 반복하는 것이 아닌, N을 i로 나누어 보며 약수인지를 확인하는 숫자 역할을 하므로, i가 1부터 N까지 돌게 한다.

11~12  | i가 N의 약수이면 cnt를 1 증가시키는 코드이다.

13~16  | cnt가 k와 같아졌을 때(i가 k번째로 작은 인수일 때) k번째 약수가 존재한다는 표시로 flag에 1을 대입하고 for문을 탈출하는 코드이다.

18~19  | flag가 1일 때(k번째 약수가 존재할 때) result에 k번째 약수인 i를 대입하는 코드이다.

20~21  | flag가 0일 때(k번째 약수가 존재하지 않을 때) result에 0을 대입하는 코드이다.

 

느낀점

 

- 약수의 개념과 산술연산자 '%'를 알고, for문을 잘 활용하면 쉽게 풀수 있는 문제인 것 같다.