[백준 문제풀이 / C++] 2981 검문

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

2981번: 검문

 

정답률 20%밖에 안되는 문제인데,

 

아마 대다수의 분들이 나처럼(?) 수학식 접근이 아니라,

 

일반적인 접근 ( ex) 입력값 정렬 후, 가장 큰 수 기준으로 for 문을 돌려, 나머지 입력값들의 나머지가 같은 지 나눠서 체크하기 )

으로 진행해서  시간초과가 났을 것이다.

 

시간복잡도를 고려해봐야하며 입력값들을 arr 배열에 넣었을때,

 

arr[i] = M * t[i]( arr[i]을 M으로 나눴을때의 몫) + r(다른 입력값들과 같은 나머지) = M*t[i]+r

 

로 나오게 된다.

 

arr[i]-arr[i-1]을 하게 될 경우,

 

arr[i] - arr[i-1] = M*(t[i]-t[i-1]) + r-r = M*(t[i]-t[i-1])  이 되게 되는데

 

결국 모든 M을 찾아야되기 때문에, 

arr[i]-arr[i-1] 들의 최대공약수를 찾고, 그것의 1이 아닌 약수를 찾으면 된다. 

( 이것들을 구하고 arr[i] 들을 나눴을때, 모두 같은 나머지를 같게 된다. )

 

ㅇ 소스 코드

#include <stdio.h>
#include <algorithm>
using namespace std;

int n;
int arr[101]={0,};
int sol[501]={0,};
int cnt = 0;


// 시간 초과
//int main(){
//    scanf("%d",&n);
//    for(int i=0;i<n;i++)scanf("%d",&arr[i]);
//
//    sort(arr,arr+n);
//
//    for(int i=2;i<arr[n-1];i++){
//        bool flag=true;
//        int tmp = arr[0]%i;
//        for(int j=1; j<n;j++){
//            if(arr[j]%i != tmp) {
//                flag=false;
//                break;
//            }
//        }
//        if(flag) printf("%d ",i);
//    }
//    return 0;
//}

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

int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d",&arr[i]);
    
    sort(arr,arr+n);
    
    int bm = arr[1]-arr[0];
    // arr[i]-arr[i-1] 의 최대공약수를 고른다.
    for(int i=2; i<n;i++){
        bm= gcd(bm,arr[i]-arr[i-1]);
    };
    
    
    // 약수 구하는 가장 빠른 방법
    // 30의 약수를 구할때, 5가 약수인걸 알면 30/5 =6 을 알 수 있는것처럼, 짝을 바로 구해나간다.
    for(int i=2; i*i<=bm;i++){
        if(bm % i==0){
            sol[cnt++]=i;
            if(i*i != bm) sol[cnt++]=bm/i;
        }
    };
    // 위 i=2 로 진행하여, 1의 짝인 bm이 들어가지 못해 넣어줌
    sol[cnt++]=bm;
    
    // 오름차순이므로, 정렬 후 출력하기
    sort(sol,sol+cnt);
    for(int i=0;i<cnt;i++){
        printf("%d ",sol[i]);
    }
    
    return 0;
}