[C++]백준 - 2981번 문제

2981번: 검문 (acmicpc.net)

2981번: 검문

 

2981번 : 검문

---

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

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

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

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

 

입력

---

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

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

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

 

 

출력

---

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

 

 

---

 

생각해 볼 점

---

나머지가 같은 수를 구하는 문제입니다.

예를 들어 [3, 39, 43]가 있다고 하면, {2, 4}가 정답이 됩니다.

N으로 나누었을 때 모두 동일한 나머지를 가지고 있다는 건 숫자들 간의 차이가 모두 N으로 나누어 떨어진다는 뜻이죠.

 

쉽게 이야기하면,

 

3 과 39의 차이는 36

39와 43의 차이는 4입니다.

 

36과 4의 공약수 모두 정답이 됩니다.

 

다른 예시를 들어볼까요?

 

[61, 83, 711]을 받았을 경우 각 수들 간의 차이는 (22, 628)이고, 이 둘의 공약수는 2 뿐이므로

답은 2 입니다.

 

따라서,

1. 우리는 수를 받아서 숫자들 간의 차이를 구합니다.

2. 해당 차이를 Set에 담습니다. (Set는 자동 정렬과 자동 중복 제거를 수행합니다.)

3. Set안의 숫자들 간의 최대 공약수를 구합니다.

4. 최대공약수의 약수를 검색하여 모두 출력합니다.

 

4번을 수행할 때, 수행 시간을 더 줄이기 위해 2부터 최대공약수의 제곱근까지만 탐색합니다.

 

예를 들어, 최대공약수가 20이면,

 

2에서 20의 제곱근 4까지 반복문으로 검색합니다.

 

for문의 수행 예시

=====================================

2 -------> 20 / 2 = 10 (2, 10은 20의 약수)

3 (약수가 아님)

4 -------> 20 / 4 = 5  (4, 5는 20의 약수)

=====================================

for 문은 총 3번 수행됩니다.

 

2, 10, 4, 5를 set에 담아 차례로 print해주면 완료입니다.

 

코드

---

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

int gcd(int a, int b)
{
    while(b > 0) // 유클리드 호제법
    {
        int temp = b;
        b = a % b;
        a = temp;
    }
    
    return a;
}
int main() {
	int N;
	set<int> interval;
	cin >> N;
	int prev; // 이전 입력
	cin >> prev;
	for(int i = 1; i < N; i++)
	{
        int input;
	    cin >> input;
	    interval.insert(abs(input - prev)); //숫자들의 차이값을 set에 저장
	    prev = input;
	}
	
	set<int>::iterator it = interval.begin();
	int g = *it;
    
	for(;it != interval.end(); it++)	//set 내부의 최대공약수 구하기
	{
	    g = gcd(*it, g);
	}
	
	set<int> result;					//최대 공약수 g의 약수를 담는 set
	result.insert(g);					//자기 자신도 약수이므로 미리 저장
    
	for(int i = 2; i <= sqrt(g); i++)	//g의 제곱근까지만 수행
	{
	    if(g % i == 0)
	    {
	        result.insert(i);			
	        result.insert(g / i);
	    }
	}
	
	for(it = result.begin(); it != result.end(); it++) cout << *it << " ";
	return 0;
}

 

그 외

---

유클리드 호제법이 자주 쓰이니 항상 암기하도록 합시다.