[백준 2981번][C] 검문 (유클리드 호제법)

---

 

정답 비율.. 문제도 잘 읽어야 하고, 시간초과도 시도할 때마다 난다

 

브루트포스로 풀면

입력 값들 중에서 가장 작은 min 수를 가지고, 1까지 -1 하면서 모든 값의 최대공약수/공약수를 구하면 된다

당연히 시간초과가 난다

 

---

 

이는 다음과 같은 수학적인 식 도출을 생각해야 한다

 

예를 들어 A, B, C 값이 입력되었다고 하자.

A = aM + r / B = bM + r / C = bM + r

식이 성립할 것이다 (M은 나머지가 모두 같게 되는 수의 집합)

 

이는 다음과 같다

|A-B| = (a-b)M / |B-C| = (b-c)M

gcd(|A-B|, |B-C|) == M

 

따라서, arr[1]-arr[0], ..., arr[N]-arr[N-1] 값들의 공약수를 구하면, 답이 도출된다

 

---

 

gcd() 함수의 코드는 유클리드 알고리즘을 사용하여 다음과 같다

 

int gcd(int a, int b)
{
    if(a % b == 0) return b;
    else return gcd(b, a%b);
}

 

(- snupi.tistory.com/78)

[Python] 유클리드 알고리즘

 

---

 

이후에, 문제를 잘 읽어보면, M 출력값은 증가하는 순서로 출력해야 한다

 

따라서 최대공약수 gcd() 값의 약수를 리스트에 저장하여

O(NlogN) 시간 복잡도로 정렬한 후, 출력하면 된다

 

나는 좀 다른 방식으로 다음과 같이 출력하였다

 

void print_cd(int n)
{
    int stack[1000]; // 메모리 사용하는 스택 이용
    int idx=0; // 큰 수부터 저장하며, 역순으로 출력한다

    stack[idx++] = n;
    for(int i=2 ; i<=sqrt(n) ; i++) // sqrt(n) 이후로는 새로운 약수가 없다
    {
        if(n%i == 0)
        {
            if(i*i == n) printf("%d ", i);
            else
            {
                printf("%d ", i);
                stack[idx++] = n/i;
            }
        }
    }

    for(int i=idx-1 ; i>=0 ; i--) // 그냥 리스트로 저장하여 qsort나 mergesort 이용 가능
        printf("%d ", stack[i]);
}

 

2부터 sqrt(n) 까지 도는 for문을 이용하여,

약수를 찾을 때 그 약수를 출력한 후,

그에 나눠지는 수를 stack에 차례대로 저장한다

이를 역순으로 출력하면 오름차순으로 출력이 가능하다

 

예를 들어 n == 10일 경우 (2, 5, 10)

- 10 -> stack[0]

- 1 -> X

- 2 -> 출력 후, 5 -> stack[1]

- stack[1] 5 출력

- stack[0] 10 출력

 

---

 

총 코드는 다음과 같다

 

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int gcd(int a, int b)
{
    if(a == 0) return b;
    if(b == 0) return a;

    if(a % b == 0) return b;
    else return gcd(b, a%b);
}

void print_cd(int n)
{
    int list[1000]; // 메모리 사용하는 스택 이용
    int idx=0; // 큰 수부터 저장하며, 역순으로 출력한다

    list[idx++] = n;
    for(int i=2 ; i<=sqrt(n) ; i++) // sqrt(n) 이후로는 새로운 약수가 없다
    {
        if(n%i == 0)
        {
            if(i*i == n) printf("%d ", i);
            else
            {
                printf("%d ", i);
                list[idx++] = n/i;
            }
        }
    }

    for(int i=idx-1 ; i>=0 ; i--) // 그냥 리스트로 저장하여 qsort나 mergesort 이용 가능
        printf("%d ", list[i]);
}

int main()
{
    int N, gcdN, min=1000000000;
    int arr[1001];

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

        if(i == 0) continue;
        arr[i] = abs(arr[i] - arr[0]); // arr[1:N-1]

        if(i == 1)
        {
            gcdN = arr[1];
            continue;
        }
        gcdN = gcd(gcdN, arr[i]);
    }
    
    print_cd(gcdN);

    return 0;
}