백준 2981번 [검문](C++)-yes6686- 티스토리

백준 문제 풀이: 2981 [검문]

---

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

문제 설명:

n개의 숫자가 주어질 때, 이를 m으로 나눴을 때 모두 같은 나머지를 가지는 m의 가능한 값을 오름차순으로 출력하는 문제입니다. 여기서 m은 1보다 커야 합니다.

---

문제 해결 코드

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

int arr[101];
set<int> s;

// 최대공약수 계산 함수
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin >> n;
    
    // 숫자 입력
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    // 배열 정렬
    sort(arr, arr + n);
    
    // 모든 인접 차이의 최대공약수 계산
    int k;
    if (n == 2) {
        k = arr[1] - arr[0];
    } else {
        k = gcd(arr[1] - arr[0], arr[2] - arr[1]);
        for (int i = 3; i < n; i++) {
            k = gcd(k, arr[i] - arr[i - 1]);
        }
    }
    
    // 최대공약수의 약수 찾기
    for (int i = 2; i * i <= k; i++) {
        if (k % i == 0) {
            s.insert(i);
            s.insert(k / i);
        }
    }
    s.insert(k);
    
    // 결과 출력
    for (auto iter = s.begin(); iter != s.end(); iter++) {
        cout << *iter << ' ';
    }
}

---

코드 설명

• 핵심 알고리즘: 인접 차이의 최대공약수를 활용해 모든 숫자를 나눌 수 있는 m의 약수를 구합니다.
• 구현 세부사항:
  • 입력된 숫자를 정렬하여 인접한 숫자들의 차이를 계산
  • 모든 차이의 최대공약수를 구하고, 이를 약수로 나눕니다.
  • 구한 약수는 set 자료구조를 이용하여 중복 없이 저장 후 정렬 출력합니다.
• 시간 복잡도:
  • 입력 정렬: O(n log n)
  • 최대공약수 계산: O(n log k), 여기서 k는 최대공약수
  • 약수 계산: O(√k)
  총 시간 복잡도: O(n log n + n log k + √k)

---

결과

주어진 숫자들로부터 조건을 만족하는 m의 값을 오름차순으로 출력합니다. 문제를 해결하기 위해 최대공약수를 기반으로 약수를 구하는 접근법을 사용했습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!