[BOJ-2981][C++] 검문

문제

트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다.

상근이는 시간을 때우기 위해서 수학 게임을 하기로 했다.

먼저 근처에 보이는 숫자 N개를 종이에 적는다. 그 다음, 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다. M은 1보다 커야 한다.

N개의 수가 주어졌을 때, 가능한 M을 모두 찾는 프로그램을 작성하시오.

 

입력

첫째 줄에 종이에 적은 수의 개수 N이 주어진다. (2 ≤ N ≤ 100)

다음 줄부터 N개 줄에는 종이에 적은 수가 하나씩 주어진다. 이 수는 모두 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. 같은 수가 두 번 이상 주어지지 않는다.

항상 M이 하나 이상 존재하는 경우만 입력으로 주어진다.

 

출력

첫째 줄에 가능한 M을 공백으로 구분하여 모두 출력한다. 이때, M은 증가하는 순서이어야 한다.

 

예제 입력 1

3
6
34
38

 

예제 출력 1 

2 4

 

예제 입력 2

5
5
17
23
14
83

 

예제 출력 2 

3

 

출처

Contest > Croatian Open Competition in Informatics > COCI 2007/2008 > Contest #6 3번

 

알고리즘 분류

• 수학
• 정수론
• 유클리드 호제법

 

문제 출처

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

2981번: 검문

 

---

 

문제 해결 방법

• 다음과 같이 직접 풀려고 하였으나 시간 초과 오류로 오답 처리되었다.

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

int N, num, maxVal, minVal;
vector<int> nums, rs;

bool checkAns(int n, vector<int> v) {
    int sum = 0;

    for (auto i : v) {
        sum += i;
    }

    if (sum == n * v[0]) {
        return true;
    }
    return false;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N;

    for (int i = 0; i < N; i++) {
        cin >> num;
        nums.push_back(num);
    }

    sort(nums.begin(), nums.end());    // 오름차순 정렬

    minVal = nums[0];
    maxVal = nums[N - 1];

    for (int i = 2; i <= minVal; i++) {
        for (int j : nums) {
            int r = j % i;
            rs.push_back(r);
        }
        if (checkAns(N, rs)) {
            cout << i << " ";
        }
        rs.clear();
    }

    return 0;
}

 

 

• 그래서 다른 방법을 찾아야 했다. 해결 방법을 찾지 못해 구글링을 통해 문제를 해결하게 되었다.
• 문제의 조건들을 식으로 나타내면 다음과 같다. ($r$ : 임의의 나머지)

$a_0 \; \% \; M = r$
$a_1 \; \% \; M = r$
$a_2 \; \% \; M = r$
...

•  위의 식을 다른 방법으로 표현하면 다음과 같다. ($r$ :  임의의 나머지, $c_{i}$ : 임의의 자연수)

$a_0 = c_0 \times M + r$
$a_1 = c_1 \times M + r$
$a_2 = c_2 \times M + r$
...

• 다음과 같이 서로의 식을 빼주면 나머지(`r`)를 제거해줄 수 있다.

$a_1 - a_0 = (c_1 - c_0) \times M$
$a_2 - a_1 = (c_2 - c_1) \times M$
$a_3 - a_2 = (c_3 - c_2) \times M$

• 좌항의 뺄셈 결과가 양수인 것들을 전부 나열하고, 이 수들의 최대 공약수를 구하면 이 문제에서 나올 수 있는 답 중 최댓값이 된다. 따라서 이 최대 공약수의 약수 중, 1을 제외한 수를 출력시켜 주면 된다.
• 특정한 수의 약수를 구할 때, 약수의 절반 정도만 구하면 나머지 부분은 바로 구할 수 있으므로, 연산을 빠르게 하기 위해 다음과 같이 코드를 작성한다.
  • 예) 12의 약수는 $\{1, 2, 3, 4, 6, 12 \}$ 이며, $\{1, 2, 3\}$ 만 구하면 1×12, 2×6, 3×4에서 나머지 약수 $\{4, 6, 12\}$ 를 자연스럽게 구할 수 있다.

for (int i = 2; i <= sqrt(gcdVal); i++) {
    if (gcdVal % i == 0) {
        factors.push_back(i);
        factors.push_back(gcdVal / i);
    }
}

• 맨 처음 구한 gcdVal의 값을 약수를 모아놓은 factors 벡터에 넣는다.

factors.push_back(gcdVal);

• 오름차순으로 출력시켜줘야 하므로, 다음과 같이 출력 전 정렬을 수행해준다.

sort(factors.begin(), factors.end());
factors.erase(unique(factors.begin(), factors.end()), factors.end());    // 중복된 약수 제거

for (int i = 0; i < factors.size(); i++) {
    cout << factors[i] << " ";
}

 

코드

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

int N, num;
vector<int> nums, factors;

int gcd(int x, int y) {
    if (x == 0) return y;
    else return gcd(y % x, x);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N;

    for (int i = 0; i < N; i++) {
        cin >> num;
        nums.push_back(num);
    }

    sort(nums.begin(), nums.end());    // 오름차순 정렬

    int gcdVal = nums[1] - nums[0];
    for (int i = 2; i < N; i++) {
        gcdVal = gcd(gcdVal, nums[i] - nums[i - 1]);
    }

    for (int i = 2; i <= sqrt(gcdVal); i++) {
        if (gcdVal % i == 0) {
            factors.push_back(i);
            factors.push_back(gcdVal / i);
        }
    }

    factors.push_back(gcdVal);
    sort(factors.begin(), factors.end());
    factors.erase(unique(factors.begin(), factors.end()), factors.end());    // 중복된 약수 제거

    for (int i = 0; i < factors.size(); i++) {
        cout << factors[i] << " ";
    }

    return 0;
}

 

채점 결과

 

참고

• [단계별로 풀어보기] > [정수론 및 조합론]
• 골드IV

 

unique()

형식

unique(ForwardIterator first, ForwardIterator last)

• 벡터(vector) 컨테이너에서 연속으로 중복된 요소를 제거하는 함수이다.
  • 컨테이너에서 중복되지 않는 원소들을 앞에서부터 채워나가는 함수이며, 남은 뒷부분에는 원본값들이 존재한다.
  • 따라서 erase() 함수와 함께 사용하여 중복 제거 후 남은 부분을 없애준다.
• 사용 전, 반드시 컨테이너가 정렬되어 있어야 한다.
• 사용하려면 <algorithm> 헤더를 불러와야 한다.

 

작동 과정

• 다음과 같이 정렬된 벡터 V가 있다.

1

2

2

3

4

4

5

 

• 다음과 같이 unique() 함수를 사용하면, 연속으로 중복되는 값 2, 4를 없앤다.

unique(V.begin(), V.end());

1

2

2

3

4

4

5

 

• 그리고 남은 부분은 원본값(4, 5)을 유지시켜 준다.

1

2

3

4

5

4

5

 

• unique() 함수는 원본이 유지된 요소들의 첫번째 주소값을 반환한다.

1

2

3

4

5

4

5

 

• 따라서 erase() 함수를 사용하여 원본이 유지된 요소들을 지워준다. (그렇지 않으면 중복 되지 않은 값들을 얻을 수 있다.)

V.erase(unique(V.begin(), V.end()), V.end());

 

• 최종적으로 벡터 V에는 중복이 제거된 요소들만 남게된다.

1

2

3

4

5