[수학] 검문 (백준 2981번)

다음 페이지에 더 있다...

 

이 문제가 '브루트포스' 라는 분류를 가지고 있는 건, 내가 봤을 때 미친 짓이다.

브루트포스 방식으로도 풀 수야 있겠지만 시간초과가 미친듯이 난다.

브루트포스로, 더 이상 효율적으로 만들 수 없을 거라고 생각이 들 때까지 했는데 90%에서 시간초과였다.

그래서 다른 방식을 찾아서 했는데도 시간초과가 미친 듯이 나왔다.

(그래서 데이터 구조와 STL을 적극 활용하였고, 최대공약수를 구하는 공식들도 훨씬 공부해야 했다.)

 

차라리 이건 '수학'만 구분으로 가지고 있는 게 낫다.

최대 값이 1000000000으로 입력될 수 있고, 같은 값이 2번 이상 입력되지 않는다고 하더라도

다른 수들과의 최대 공약수가 아무리 작아도 500000000은 나올 수 있을 텐데,

이걸 1부터 브루트포스로 검사를 한다고?

미친 짓이다.

절대 불가능하다.

 

그래서 최대 공약수에 대하여 절반만 검사하는 방법도 생각해보았고,

양쪽 항이 짝을 이룬다는 점 (양쪽 항의 곱은 항상 일정하다.)을 이용하기도 해봤는데,

전부 다 시간초과가 떴다.

 

시행착오를 겪어가며 모든 줄을 효율적으로 만들어 갔다.

모르는 부분은 구글링을 통해서 찾아 보았는데, 그냥 최대공약수 구하는 공식은 닥치고 외우는 게 낫겠다.

이걸, 안 보고, 생각해낼 수 있을까?

이건 정말 수학자의 영역이 아닐까? (아무리 내가 공학도라고 하지만 너무하다.)

지금도 숫자 마술을 보는 것마냥 알쏭달쏭하기 짝이 없는데, 이런 공식을 유도해낼 수 있을까?

(일단 내가 종이없이 프로그래밍을 하긴 했지만.)

 

아래는 문제와, 최종적인 코드다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int n;
// long long int arr[100];
// 벡터로 대체하고자 한다.
//long long int tmp[100];
 
int GCD(int a, int b)
{
    if (a % b == 0)
        return b;
 
    return GCD(b, a % b);
}
// 만약 7하고 14가 주어지면, 7 % 14 != 0 이므로 GCD(14,7)로 변경되고 7 출력
// 만약 6 18이 주어지면 마찬가지로 GCD(18,6)으로 변경되고 출력.
// 만약 7 18이 주어지면, 마찬가지로 GCD(18,7)로 변경이 되고,
// 이 경우에는 또 나눠지지 않으므로 GCD(7,2)로 변경되고,
// 다시 GCD(2,1)로 변경되고, GCD(1,2)로 변경된다.
// 최대 공약수를 이런 방식으로 구할 수 있다는 것을 처음 알았다.
 
// 나는 for문을 2개 중첩해야만 가능했고, 극한으로 줄인 결과 시간초과 (90%)...
 
int main(void)
{
    //    int a, b;
    //    cin >> a >> b;
 
    //    cout << GCD(a, b); 최대 공약수가 제대로 출력되는지 확인했다.
 
    int n;
    //    cin >> n;
    scanf("%d", &n);
 
    vector<int> arr(n);
    for (int i = 0; i < n; i++)
        cin >> arr[i];
//        scanf("%lld", &arr[i]);
 
    sort(arr.begin(), arr.end());
    int temp = arr[1] - arr[0];
    // 일단 arr[0]에 대해 아무 값 하나와의 차이 값을 구한다.
 
    for (int i = 2; i < n; i++)
        temp = GCD(temp, arr[i] - arr[i - 1]);
    //    temp = abs(temp);
 
        // 그리고 그렇게 구한 temp값에, 모든 index의 차이에 대한 배열 값의 3최대공약수를 구한다.
        // 논리적 중첩이기 때문에 당연히 모든 배열에 대한 최대공약수가 나올 수밖에 없다 (!!!)
        // 여기서 temp는 음수가 나올 수 있다, 이게 싫으면 arr[i] = arr[i-1]을 절댓값으로 하거나 정렬하라.
 
    //    for (int i = 2; i <= temp; i++)
        //  if (temp % i == 0) cout << i << ' ';
    //        if (temp % i == 0) printf("%d ", i);
    //  지금도 90%에서 시간초과가 나는데, 아무래도 출력 방식을 바꿔야 할 거 같다.
 
    //    int count = 0;
    //    for (long long int i = temp; i >= temp / 2; i--)
    //    {
    //        if (temp % i == 0)
    //        {
    //            tmp[count] = i;
    //            count++;
    //        }
    //    }
    //    for (int i = count -1; i >= 0; i--)
    //    {
    //        printf("%lld ", tmp[i]);
    //    }
        // 이젠 제발 통과시켜줘.
        // 1000000000의 값도 넣을 수 있다고 되어 있어서 범위를 수정해주었다.
 
        // 더 느려졌다, 18%에서 멈춘다.
        // 아 좋은 생각이 났다, 생각해보니 약수들은 시작과 끝점으로부터 쌍을 이룬다는 점을 이용하면 된다.
        // 500000000까지 연산할 필요가 없어졌다.
        // 데이터를 삽입 후 정렬하고, 다시 출력해주면 될 거 같다.
 
    vector<int> ans;
    for (int i = 2; i * i <= temp; i++)
    {
        if (temp % i == 0)
        {
            ans.push_back(i);
            ans.push_back(temp / i);
        }
    }
    ans.push_back(temp);
    sort(ans.begin(), ans.end());
 
    ans.erase(unique(ans.begin(), ans.end()), ans.end());
    // unique는 algorithm header에 있는 함수로, 중복된 값을 쓰레기 index로 보내버리는 함수다.
    // unique 함수는 이 쓰레기 index의 시작점을 반환하기 때문에 erase 함수의 두번째 매개변수로 end를 전달하면,
    // ans의 size를 효과적으로 줄일 수 있다.
 
    for (int i = 0; i < ans.size(); i++)
    {
        printf("%d ", ans[i]);
    }
}

 

느낀 점

 

나는 아직 프로그래밍을 공부한지 5개월 밖에 되지 않았고, 문제 풀이는 그보다 더 짧다.

그래서 다른 사람들의 코드를 볼 때마다 아름답다고 생각할 때도 있고,

그 사람들의 발상력에 대해서는 감탄을 멈출 수가 없다, 어떻게 이렇게 효율적이고, 코드가 깔끔한지.

 

그러하다.

 

내 블로그 조회수는 지금까지 다 합쳐봐야 40도 안 나오는 수준이지만 (아마 그 중 대부분은 나겠지?)

내 블로그를 우연히 본 사람들이, 이 글에서 주인장이 병신이라는 것을 알았으면 좋겠다.

내가 다른 사람들의 블로그를 볼 때 느꼈던 기분이 즐거움만 있던 게 아니고, 열등감도 있었기 때문에,

내가 달랑 답만 놓고가면, 혹시라도 이걸 보는 사람이 나랑 같은 기분을 느낄까봐 걱정이다.

세상 누가 초보 단계를 건너 띄고 시작할까!