[백준] 1684번 같은 나머지 (C++)

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

 

 

이 문제는 N개의 정수가 주어졌을때 각각의 정수에 대해서 D로 나누었을때 같은 나머지가 나오는 수에 대한 가장 큰 D를 찾는 문제이다.

 

수열의 개수는 최대 1000개이며 1부터 탐색하여 100000만까지 탐색하는 경우 10억으로 시간초과가 나기 때문에

 

다른 방법을 사용하여 해결해야한다.

 

 

즉 문제에 나온 식을 전개하여 풀어썼을때 위 식이 나오며 두수의 차이는 나누는 수의 배수이므로 두 수의 차이의 약수 중 하나이며

 

이것을 해결하기 위해서 정렬후 가장 작은 값을 빼주며 최대공약수를 구하면 쉽게 해결할 수 있다.

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

int dx[] = {-1, 1, 0, 0, 1, -1, -1, 1};
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int N;

void solve(vector<int> &v) {
    vector<int> tmp;

    sort(v.begin(), v.end());

    for(int i = 1; i < N; i++) {
        tmp.push_back(v[i] - v[0]);
    }
    
    int answer = gcd(tmp[0], tmp[1]);

    for(int i = 1; i < N; i++) {
        answer = gcd(answer, tmp[i]);
    }

    cout << answer;
}

void input() {
    cin >> N;

    vector<int> v(N, 0);

    for(auto &it : v) {
        cin >> it;
    }

    solve(v);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
}

 

 

회고록

문제를 보고 완전탐색할순 없겠다 생각해서 뭔가 느낌이 유클리드 호제법을 사용해서 풀어야된다고 생각은 했는데

식을 전개해서 두수의 차이의 약수를 구하는 것까지 생각을 못했다.

앞으론 문제에 나온 식들을 유심히 살펴보며 새로운 것을 시도하는 습관을 가져야겠다.