실력키우기 약수(C++)

2809 : 약수

제한시간: 1Sec    메모리제한: 32mb
해결횟수: 471회    시도횟수: 1895회   

한 개의 정수를 입력받아 입력받은 정수의 약수를 모두 출력하는 프로그램을 작성하시오.

 

정수 N이 주어진다. (2 ≤ N ≤ 21억)

N의 약수를 작은 수부터 차례로 모두 출력한다.

[Copy] 24

[Copy] 1 2 3 4 6 8 12 24

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

/**************************************************************     Problem: 2809     User: a132034     Language: C++     Result: Success     Time:0 ms     Memory:1764 kb ****************************************************************/     #include    <iostream> #include    <algorithm> using namespace std;   bool Greater(int i, int j){ return i < j; } int main() {     int N;     int sq;     int arr[10000], cnt = 0;     cin >> N;     sq = (int)sqrt(N);       for (int i = 1; i <= sq; i++) {         if (N % i == 0) {             arr[cnt++] = i;             if (N / i != i) arr[cnt++] = N / i;         }     }     sort(arr, arr + cnt, Greater);     for (int i = 0; i < cnt; ++i)         cout << arr[i] << " ";     return 0; }

이 문제같은 경우 도움말이 너무 잘나와있어서 정렬만 구현하면 되는 문제였다. 

도움말은 아래와 같다. 

------------------------------------------------------------------------------------------------------------------------------------------------------------------------

코드1
 01    for (i = 1; i <= N; i++) {
 02        if (N % i == 0) {
 03            printf("%d ", i);
 04        }
 05     }

코드분석
1부터 N까지 N의 약수인지 모두 확인하여 출력하는 프로그램이다. 
그런데 위와 같이 작성하면 N이 21억이 입력이 되었을 때 1부터 21억까지 21억개의 수를 확인해 보아야 한다. 
당연히 시간초과의 위험이 있으니 프로그램을 수정하여 시간을 줄여보도록 하자.

코드2
 01    int sq;                                   // N의 제곱근을 저장하기 위해
 02    int arr[10000], cnt=0;                    // N의 약수를 저장하기 위해
 03    scanf("%d", &N);
 04    sq = (int)sqrt(N);                         // N의 제곱근을 구하여 sq에 저장한다. 
 05    for (i = 1; i <= sq; i++) {
 06        if (N % i == 0) {
 07            arr[cnt++] = i;                    // 작은수 저장
 08            if (N / i != i) arr[cnt++] = N / i;   // 큰수 저장 (작은수와 같지 않을 경우)
 09        }
 10    }
 11    // 이 부분에는 arr배열에 저장된 값을 정렬하여 모두 출력하도록 스스로 작성해보자.

코드분석
 위 프로그램은 N의 제곱근까지만 반복문을 실행해서 모든 약수를 구하는 프로그램이다.
 만약 N이 100이라고 가정하고 100의 약수를 모두 구해보면
  1 * 100 = 100
  2 *  50 = 100
  4 *  25 = 100
  5 *  20 = 100
 10 *  10 = 100

위와 같이 성립하므로 100의 약수는 1 2 4 5 10 20 25 50 100 이렇게 9개가 된다.
그런데 2가 100의 약수라는 것을 알게 된 순간 50이라는 약수도 구할 수 있게 된다.
즉 a * b = 100일 경우 a를 알게 되면 b를 구할 수 있다는 것이다.
그러므로 두 수의 곱이 N일 경우 그 두 수는 N의 약수이며 두 수중 작은 수의 범위는 1~(루트100) 이하가 된다.
위의 경우 10 * 10 = 100 이므로 10 이상의 수는 두 수의 곱으로 나타낼 경우 큰 수에 해당하므로 작은 수를 저장할 때 함께 저장이 되어 있는 것이다.

04 : sqrt는 제곱근을 구하는 함수이며 double형으로 리턴되므로 (int)를 붙여서 정수형으로 변환한 것이다.
08 : N이 100일 때 i가 10이면 작은 수와 큰 수가 모두 10이므로 작은 수 한 번만 저장하면 된다.
05 : 1부터 N의 제곱근까지 반복한다. 제곱근을 구하는 것이 번거롭다면 부등호의 양변을 제곱하여 아래와 같이 작성해도 된다.
        for (i = 1; i * i <= N; i++)

------------------------------------------------------------------------------------------------------------------------------------------------------------------------

코드 1과 같은 방법을 사용한다면 구할 수 있으나 시간이 오래 걸려 시간초과가 날 것이기 때문에 시간을 줄일 수 있는 방법을 생각해 본다. 

여기서 말하는 이론은 

1. 두 수를 곱해서 N이 나오면 두 수가 모두 N의 약수이다.

2. 1에서 나온 두 수는 큰 수와 작은 수로 나뉠 수 있다. 

3. 작은 수의 범위는 분명 sqrt(N) 이하가 될 것이고, 큰 수의 범위는 분명 sqrt(N)이상이 될 것이다. 

때문에 작은 수 까지만 반복을 하며 작은 수를 구했을 때 큰 수를 동시에 저장해주면 된다. 

남은 것을 출력을 위한 정렬인데, 이경우 사실 저장하는 패턴이 cnt를 갯수로 보았을 때 

0 cnt-1 1 cnt-2... 순서로 저장되기 때문에 더 깊이 생각해 본다면 정렬 없이도 출력이 가능할 것이지만 

stl sort기능을 사용해볼 겸 정렬을 한 후 출력하였다. 

stl sort기능은 algoritm을 include하면 사용할 수 있으며 

기본적으로 배열의 시작주소와 끝주소를 주면 int형의 경우 다른 인자를 줄 필요 없이 작은 숫자부터 정렬이 된다. 

굳이 Greater라는 비교함수를 만들어 준 이유는 보기 편하기 위해서이다. 비교함수를 세번째 인자로 넘겨주면 비교함수에 따라 참이되는 방향으로 정렬해준다. 클래스나 구조체 등을 사용할 때에도 동일하게 비교함수를 사용해주면 편하게 정렬할 수 있다.