https://www.acmicpc.net/problem/1684
문제
> 정수 N을 정수 D로 나눴을 때의 몫을 Q, 나머지를 R이라고 하면 항등식 R = N - Q×D가 성립한다.
> n개의 정수로 된 수열이 있을 때, 모든 정수를 한 정수 D로 나눴을 때 나머지가 같아지는 경우가 있다.
> 그리고 수열에 따라서는 이러한 정수 D가 여러 개 존재할 수 있다.
> n개의 정수로 된 수열이 주어졌을 때, 가장 큰 D를 구하는 프로그램을 작성하시오.접근
문제가 주어진 n개의 정수를 한 정수 D로 나누었을 때 나머지가 모두 같아지는 경우가 있다고 한다.
이 경우를 예제에 주어진 수들로 문제의 식으로 정리해보면
R = 701 - Q1xD
R = 1059 - Q2xD
R = 1417 - Q3xD
R = 2312 - Q4xD
가 된다.
그럼 이 우변들이 모두 같다는 듯이므로 이를 두개 씩 짝 지어 다시 식을 정리해보면 아래와 같다.
(Q2 - Q1)xD = 358
(Q3 - Q2)xD = 358
(Q4 - Q3)xD = 895
문제에서 모든 한 정수 D라고 했으므로 여기의 D는 모두 같은 수 이다. 즉, 우변에 있는 수들은 D에 뭔가를 곱한 수들 다시 말해 D의 배수가 되고 또 이 D는 우변에 있는 수들의 공약수가 된다.
결국 구해야하는건 D중 가장 큰 수이므로 이 우변에 있는 수들의 최대공약수를 구하면 된다.
문제해결
> 정수들의 개수를 입력받고 그 수 만큼 입력받아 num벡터에 저장한다.
> 입력받은 수 중 두 수의 차를 이용하기 위해 연속된 두 수끼리 차를 구해 n-1크기의 diff벡터에 저장한다.
> 이 diff벡터를 가지고 재귀함수인 Result에 시작값으로 0을 넣어 호출한다.
> Result함수에선 인자 start에 대해 start가 diff의 마지막 원소인지 확인한다.
아니라면 재귀인 Result(start+1)과 diff[start]의 gcd 연산을 리턴한다.
> 계속 재귀로 들어가 결국 start가 diff의 마지막 원소의 인덱스까지(size()-1)까지 도달하면 diff[start]의 값을 리턴한다.
> 이로 인해 그동안 의 쌓였던 gcd 연산이 행해진다.
예를들어 예제 2로 보면 diff의 크기는 4이므로 Result(3)에서
이 조건에 걸려 diff[3]을 반환하면
diff[3]과 diff[2]의 gcd연산이 행해진다.
> 이 gcd연산의 결과가 return 되면 또 이 결과와 diff[1]의 gcd연산이 행해지고
다음은 그 결과와 diff[0]의 gcd 연산이 행해진다.
> 그렇게 가장 처음 들어왔던 Result(0)의 결과가 리턴되고 그게 최종 결과이다.
> gcd연산은 두 수를 입력받아 (ex - Result(2), diff[1]) 두 수 중 큰 수가 앞에 와야하므로 비교해 swap으로 정렬해주고
b인 나누는 수, 즉 분모가 0이 될 때까지 gcd연산, 유클리드호제법을 반복한다.
> a를 b로 나눈 나머지를 r에 저장하고, a에 b를 b에 r을 다시 저장해 수를 줄여나가며 두 수의 최대 공약수를 구한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
int n;
vector<int> num;
vector<int> diff;
int gcd(int a, int b)
{
if (a < b) swap(a, b);
while (b != 0)
{
int r = a % b;
a = b;
b = r;
}
return a;
}
int Result(int start)
{
if (start == diff.size() - 1)
return diff[start];
return gcd(Result(start + 1), diff[start]);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n;
num.resize(n);
for (int i = 0; i < n; i++) cin >> num[i];
diff.resize(n - 1);
for (int i = 1; i < n; i++) diff[i - 1] = abs(num[i] - num[i - 1]);
cout << Result(0) << '\n';
}
후기
규칙을 찾는게 어려웠다.
얻어낸 수들의 최소 공배수를 구하기 위해 재귀를 써봤는데 문제 없이 잘 나와서 좋다.
