[백준 2981번] 검문 (C++)

문제링크 : https://www.acmicpc.net/problem/2981

2981번: 검문

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, arr[101];
set<int>result; //중복제거

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    cin >> N;
    for(int i=0; i<N; i++)
    {
        cin >> arr[i];
    }

    int tmp = abs(arr[1]-arr[0]);
    for(int i=2; i<N; i++) 
    {
        tmp = gcd(tmp, abs(arr[i]-arr[i-1])); //최대공약수 찾기
    }

    result.insert(tmp); //최대공약수 저장
    for(int i=2; i*i <= tmp; i++) //최대공약수의 약수 찾기 (1보다 커야함)
    {
        if(tmp%i) continue;
        result.insert(i); //약수
        result.insert(tmp/i); //반대편 약수
    }

    for (auto i : result) cout << i << " ";
}

 

시간초과가 나지 않는 풀이과정에 대해 이해하는데 다소 시간을 소비했던 문제이다.

수학적 접근이 필요한 문제에 많이 약했기에 풀어봤던 문제인데, 혼자 힘으로 풀이가 불가능하여 풀이를 봤음에도 한눈에 이해가 가지 않아 스스로 써보면서 풀이를 체득할 때까지 조금 걸렸던 것 같다.

 

먼저 현재 arr 값에 대해 다음과 같은 식을 세울 수 있다.

arr[0] = arr[0]에 대한 몫 (이하 몫[i]) * M + r(나머지)
arr[1] = 몫[1] * M + r
arr[2] = 몫[2] * M + r
.
.
.
arr[i-1] = 몫[i-1] * M + r
arr[i] = 몫[i] * M + r

 

위를 이용하여 또 다음과 같은 식을 찾을 수 있다.

arr[1]-arr[0] = (몫[1]-몫[0])*M
arr[2]-arr[1] = (몫[2]-몫[1])*M
.
.
.
arr[i]-arr[i-1] = (몫[i]-몫[i-1])*M

 

위 식을 통해 알 수 있는 것은 모든 경우에 M이 공통적으로 존재한다는 것이다.

따라서 공약수가 존재한다는 것을 알 수 있고 이어서 GCD 함수를 통해 최대공약수를 구해주고 해당 최대공약수의 약수를 구해주면 된다는 것을 알 수 있었다.

 

GCD 함수에 값을 넘겨줄때 주의할점이 있는데, 바로 값이 넘겨주는 대상이 (arr[i]-arr[i-1])이기 때문에 음수가 존재할 수 있다.

따라서 절대값(abs)를 씌워주거나, 입력받은 arr 배열을 오름차순으로 정렬해주는 것이 필요하다.

 

맨 처음 기본 값으로 arr[1]-arr[0]을 두고 i=2~<N까지 최대공약수를 계속 갱신해주면 된다.

이렇게 구한 최대공약수도 M이 될 수 있는 수이기에 바로 결과값을 담을 set에 담아주었다.

굳이 set으로 선언한 이유는 해당 문제에서 M은 증가하는 순서여야한다고 했는데, 이를 알아서 처리해주고 중복값도 동시에 편하게 제거하기 위함이다.

 

이후 약수값이 1보다 커야하기 때문에 i=2부터 최대공약수인 tmp까지 반복문을 돌리며 약수를 찾아준다.

현재 i가 약수라면, 그 반대편에 해당하는 tmp/i도 약수이기 때문에 이를 이용해 약수 찾는 시간을 줄여줬다.

이렇게 result에 약수들이 담기게 되고 이를 개행이 아닌 한칸 공백포함으로 출력해주면 된다.