2981 검문문제

검문은 영어로 SwordGate이다.

유난히 정답률이 낮은 문제인데
직관적인 풀이법은 시간초과가 나서 그런거같다.

컴퓨터 성능이 발달하니깐 실제 코테에서는 시간좀 낭낭하게 주면 좋겠다...

문제의 조건을 정리하면
1. N개의 숫자를 입력받는다.
2. 이 입력받은 숫자들을 M으로 나누면 나머지가 전부 똑같은 M이 무조건 하나는 있다.
3. M을 구해서 출력해라

처음에는

시간같은거 생각하지말고 일단 쭉 풀어보기로 했다.

제일 먼저 생각한게 1부터 10억까지 반복하면서 싹 모든 n들에 대입해보고 나머지를 비교하는것였다.

근데, 어차피 n값들중 최대값 이상으로 가면 더 이상 계산할 필요가 없어서 일단은 n값중 최대값까지만 계산해보기로 했다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n;

int main() {
    cin >> n;
    vector <int> vec;
    vector <int> vec2;

    for (int i = 0; i < n; i++) {
        int val;
        cin >> val;
        vec.push_back(val);
    }
    sort(vec.begin(), vec.end());

    for (int i = 1; i <= vec.back(); i++) {
        bool flag = true;
        int temp = vec.front() % i;
        for (int elem : vec) {
            if (temp != elem % i) {
                flag = false;
                break;
            }
        }
        if (flag) vec2.push_back(i);
    }

    for (int i = 1; i < vec2.size(); i++) cout << vec2[i] << " ";
}

뭔가 대충봐도 시간초과가 날 것 같은 코드이다.

두번째

그래서 생각한게 최대공약수이다. 어차피 최대공약수보다 더 큰수로 나누면 특정수들은 나머지가 고정으로 나올것이기 때문이다.

근데 잘못생각했다. 별 의미가 없다...

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int gcd(int a, int b);


int n;
int counter = 1;

int main() {
    cin >> n;
    vector <int> vec;
    vector <int> vec2;

    for (int i = 0; i < n; i++) {
        int val;
        cin >> val;
        vec.push_back(val);
    }
    sort(vec.begin(), vec.end());

    int com_gcd = gcd(vec[0], vec[1]);

    while (counter < vec.size() && com_gcd != 1) {
        counter++;
        com_gcd = gcd(com_gcd, vec[counter]);
    }

    int rang = com_gcd;
    if (com_gcd = 1) rang = vec.back();

    for (int i = 1; i <= rang; i++) {
        bool flag = true;
        int temp = vec.front() % i;
        for (int elem : vec) {
            if (temp != elem % i) {
                flag = false;
                break;
            }
        }
        if (flag) vec2.push_back(i);
    }

    for (int i = 1; i < vec2.size(); i++) cout << vec2[i] << " ";
}

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

답은?

젤다

정리해보니, 다음과 같은 원리다.

arr에 값들을 입력받는다고 하자.

arr[i] = M * ( arr[i] / M) + (같은 나머지) = M*t[i]+r 

의 구조이다.

따라서,

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]의 gcd를 찾고, 그 값들의 1을 제외한 약수를 구해야한다.