[c++] 백준 2981 - 검문

0. [c++] 백준 2981 - 검문

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

1. 풀이

1) 무식하게 풀기

처음에는 직접 모든 수를 나누는 과정을 통해서 정답을 구하려고 생각을 하였다.

무작정 모든 과정을 반복하는 것이 아닌, sort()를 활용하여 오름차순으로 구성하고, arr[1]까지만 나눠질 수 M이 커지도록 제한하고, 이 범위 내에서 arr[T-1]까지 반복을 하며 나머지가 모두 동일한지 확인하는 구조로 설계를 해보았다.

arr[1]까지 확인을 한 이유는, 오름차순으로 정렬된 arr[]배열에서 arr[1]의 범위를 넘어서는 M으로 모든 수를 나눈다고 생각을 해보자.

arr[0] % (arr[1] + 1) = arr[0]

arr[1] % (arr[1] + 1) = arr[1]

이때, arr[]를 M으로 나눈 나머지가 동일하기 위해서는

"arr[1] = arr[0]" 이여야 성립을 한다.

허나, 문제의 조건을 확인해보면, 입력으로 '같은 수가 두 번 이상 주어지지 않는다.'라는 조건이 주어져있었다.

그러면 "arr[1] = arr[0]"의 조건은 절대 성립 불가능하다는 것을 알게된다.

즉, M으로서 검색을 하는 범위는 M<arr[1]이란 걸 알 수 있다.

이러한 조건들을 가지고 최대한 시간을 줄이기 위해서 쓸모없는 계산이 되버리면 break로 함수를 탈출시키며 구현을 해보았지만... 간당간당하게 시간초과를 막을 수가 없었다. ㅠㅠ

정말 슬프지만 이 방법은 포기할 수 밖에 없었다.

2) 수학적인 접근

이번에는 수학적으로 접근을 해보았다. 이 접근은 사실 구글링을 통해 찾아보았다. 풀이를 올려주신 분들에게 감사드립니다!

일단 설명을 해보지만, 더 자세한 설명이 필요하신분은 여기서 봐주시길 바랍니다.

우선 조건에 맞춰서 M으로 나눴을 때, 나머지가 모두 동일하게 만족한 경우라고 가정을 하자.

그러면 밑의 조건을 만족하게 된다.

arr[1] % M = arr[1] - (arr[1] / M) * M

arr[2] % M = arr[2] - (arr[2] / M) * M

arr[3] % M = arr[3] - (arr[3] / M) * M

...

이 조건을 서로 빼주어보자.

그러면 아래와 같이 정리를 할 수 있게 된다.

arr[2] - arr[1] = M * (arr[2] / M  -  arr[1] / M) 

arr[3] - arr[2] = M * (arr[3] / M  -  arr[2] / M) 

...

arr[N] - arr[N-1] = M * (arr[N] / M - arr[N-1] / M )

이때, 규칙성을 생각해보면, arr[N] - arr[N-1]을 한 것은 'M*x' 라는 공통점이 있다는 것을 확인할 수 있다.('arr[2] / M  -  arr[1] / M'는 임의의 상수임으로 x로 치환)

즉, 반복문을 돌려 arr[k] - arr[k-1]들의 최대 공약수를 구한다면, M을 구해 낼 수 있게 된다.

또한, M으로 나누었을 때, 나머지가 같다는 것은 M의 약수로 나누었을 때에도 나머지가 같다는 것과 동일하다.

따라서, M을 구한 이후, M의 약수를 구하는 코드를 구현해 보았다.

+) 처음에 M의 약수를 sol[101]에 담아서 우연히 테스트를 통과하였지만, sol의 크기는 적어도 sol[500]은 넘겨야 안전하지 않을까 하는 생각이 든다.

+) 그래서 T까지 약수의 개수 최대값을 출력하는 코드도 추가로 만들어보고, 1에서 1억까지중 가장 큰 약수의 개수를 출력해 보려고 소스를 돌렸지만.... 20분째 정답이 나오질 않고있다. ㅋㅋㅋ

뭐, 약수가 나오는 개수들을 보니 1억 까지는 500을 넘는 것은 없을 것 같다만 그래도 최대값이 궁금하기는 하네.

나중에 더 찾아보자.

2. 소스코드

시간 초과로 오류가 난 알고리즘

#include<iostream>
#include<algorithm>
 
using namespace std;
 
int arr[102];
 
void calc(int T) {
    for (int M = 2; M < arr[1]; M++) {
        int flag = 0;
        int check = arr[0] % M;
        for (int i = 1; i < T; i++) {
            if (check != arr[i] % M) {
                flag++;
                break;
            }
        }
        if (flag == 0)
            cout << M << " ";
    }
    cout << endl;
}
 
 
int main() {
    int T;
    cin >> T;
    for (int i = 0; i < T; i++) {
        cin >> arr[i];
    }
    sort(arr, arr + T);
    calc(T);
}

정답을 통과한 알고리즘

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int arr[101];
 
int sol[101];    //이거 통과한 기념을 나뒀지만 sol[500]으로 수정
 
int gcd(int a, int b) {
    return a % b ? gcd(b, a%b) : b;
}
 
 
int main() {
    int n, include_m, i, count(0);
    cin >> n;
    for (i = 0; i < n; i++)
        cin >> arr[i];
    sort(arr, arr + n);
 
    include_m = arr[1] - arr[0];
    for (i = 2; i < n; i++)
        include_m = gcd(include_m, arr[i] - arr[i - 1]);
 
    for (i = 1; i*i <= include_m; i++)
        if (include_m%i == 0) {
            sol[count++] = i;
            if (i != include_m / i) sol[count++] = include_m / i;
        }
 
    sort(sol, sol + count);
    for (int i = 0; i < count; i++) 
        if (sol[i] != 1)
            cout << sol[i] << " ";
    
}

약수의 개수를 출력하는 알고리즘

#include <iostream>
 
int Max(int a, int b) {
    return a > b ? a : b;
}
 
int main() {
 
    int T, i, count = 0, MAX(0);
    std::cin >> T;
    for (int k = 2; k < T; k++) {
        count = 0;
        //절반을 뚝 짤라서 반이 있으면 나머지 반도 있는것
        for (i = 1; i*i < k; i++) {
            if (k%i == 0)
                count += 2;
 
            //정 중앙은 1개 추가.
            if (i*i == k)
                count++;
        }
        MAX = Max(MAX, count);
        std::cout << k << "의  개수 : " << count << std::endl;
    }
    std::cout << "가장 많은 약수의 개수 : " << MAX << std::endl;
    return 0;
}

3. 참고

자세한 설명

https://pangsblog.tistory.com/62

c++ 코드 참고

https://coloredrabbit.tistory.com/48

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!