[C언어] 백준 1037번 약수

 

링크

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

1037번: 약수

 

 

 

 

 

문제

---

양수 A가 N의 진짜 약수가 되려면, N이 A의 배수이고, A가 1과 N이 아니어야 한다. 어떤 수 N의 진짜 약수가 모두 주어질 때, N을 구하는 프로그램을 작성하시오.

 

 

 

 

입력

---

첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되지 않는다.

 

 

 

출력

---

첫째 줄에 N을 출력한다. N은 항상 32비트 부호있는 정수로 표현할 수 있다.

 

 

 

 

예제 입력 1

---

2
4 2

 

예제 출력 1

---

8

 

 

예제 입력 2

---

1
2

 

예제 출력 2

---

4

 

 

예제 입력 3

---

6
3 4 2 12 6 8

 

예제 출력 3

---

24

 

 

예제 입력 4

---

14
14 26456 2 28 13228 3307 7 23149 8 6614 46298 56 4 92596

 

예제 출력 4

---

185192

 

 

 

 

 

아이디어 스케치

---

- 진짜 약수란 어떤 수의 약수 중 1과 N을 제외한 나머지 약수들을 칭한다.

- 약수를 내림차순으로 정렬했을 때 가운데 약수를 기준으로 대칭곱을 하면 자기 자신이 나온다.

- 예를들어 36의 약수는 1 2 3 4 6 9 12 18 36 인데 가운데 숫자 6을 기준으로 1과 36, 2와 18, 3과 12, 4와 9 약수의 갯수가 홀수 일때는 가운데 숫자를 제곱하면 된다.

- 이 원리를 이용하여 주어진 진짜 약수들을 내림차순 정렬한 후 가장 작은 숫자와 가장 큰 숫자를 곱해주면 N을 구할 수 있다.

 

 

 

전체 코드

---

#include <stdio.h>
#include <stdlib.h>
int compare(const void* first, const void* second)
{
    int a = *(const int*)first;
    int b = *(const int*)second;

    if (a < b)
        return -1;
    else if (a > b)
        return 1;       //내림차순 정렬
    else
        return 0;
}

int main()
{
    int N;
    int* arr;
    int result;

    scanf("%d", &N);

    arr = (int*)malloc(sizeof(int) * N);

    for (int i = 0; i < N; i++)
        scanf("%d", &arr[i]);

    qsort(arr, N, sizeof(arr[0]), compare);     //퀵 정렬

    result = arr[0] * arr[N - 1];       //1과 자기 자신을 제외한 약수 중 가장 작은 약수와 가장 큰 약수의 곱

    printf("%d", result);

    free(arr);

    return 0;

}

 

 

 

 

 

 

 

제출 결과

---