백준 1037번 약수 [C언어]

문제 출처: https://www.acmicpc.net/problem/1037

 

Sol)

#include <stdio.h>

int main()
{
    int a_divisor = 0; //약수를 입력받을 변수
    long long max = 0, min = 1000001; //입력받은 약수중 최대값과 최소값을 각각 저장할 변수

    int num_of_divisors; //약수의 개수를 저장할 변수
    scanf("%d", &num_of_divisors);

    for(int i = 0; i < num_of_divisors; i++){ //약수의 개수만큼 약수를 입력받으며 
        scanf("%d", &a_divisor);

        if(a_divisor > max)                 //그중 최대값과 최소값을 찾는다.
            max = a_divisor;
        if(a_divisor < min)
            min = a_divisor;
    }

    printf("%lld\n", max * min);

    return 0;
}

 

• 풀이 방향

1과 자기 자신을 제외한 모든 약수가 중복을 제거하고 주어진다. 일반적으로 우리가 어떤 수의 약수들을 구하는 방식은 이렇다.

1과 약수를 구하는 수(자기 자신)를 써놓고, 두 수 사이에 있는 값을 2부터 오름차순으로 검사해 나가며 약수를 구하는 수(자기 자신)가 나누어 떨어지면 그 수를 적고 다음 수를 검사하며 약수를 구하는 수(자기 자신)에 다다를 때까지 해당 과정을 반복한다.

ex) 16의 약수를 구할 때: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 

      16의 약수를 오름차순으로 정리하면 1 2 4 8 16 처럼 페어가 생기게 된다. 이 페어들을 곱하면 16이 된다. 

그렇다, 복잡하게 생각할 것 없이 이 '페어'를 찾으면 쉽게 풀 수 있는 문제가 된다. 1과 자기 자신을 제외한 모든 약수를 중복을 제거하고 준다고 했으므로 가장 쉽게 찾을 수 있는 페어는 주어진 약수에서 가장 작은 값과 가장 큰 값으로 이루어진 페어가 되겠다. 16을 예로 들면 2와 8 페어가 되는 것이다.

 

• 풀이

입력받은 약수들을 배열에 저장한 후 오름차순으로 정렬해서 최대 최소를 구해도 되지만 어차피 우리가 관심 있는 것은 다른 값들이 아닌 '가장 작은 값'과 '가장 큰 값'이다. 나머지 수들은 필요가 없으므로 입력받는 순간 바로바로 비교해서 max값과 min값만 취한다. 이 max값과 min값은 페어일 것이므로 max * min 값을 하면 원래 수가 나올 것이다. 만일 입력된 약수 값이 하나일지라도 해당 약수 값은 max변수와 min변수에 각각 할당될 것이므로 답은 올바르게 나오게 된다.

 

• 주의할 점

문제에서 32비트(8바이트)의 부호있는 정수로 표현할 수 있다고 했으므로 max와 min을 long long형으로 선언해 주어야 한다. 이들을 int로 선언해주고 출력만 %lld, long long형으로 하게 되면, integer overflow를 대비할 수 없다. int끼리의 연산 결과가 int이기 때문에 max * min 의 결과가 overflow 된 상태로 %lld로 들어올 것이기 때문이다.