문제 개요
이 글에서는 주어진 배열의 모든 요소로 나눈 나머지가 서로 동일해지는 정수 k를 찾는 프로그램을 다룹니다.
예를 들어 다음과 같은 배열이 주어졌다고 가정해 보겠습니다.
arr = {12, 22, 32}이 경우 조건을 만족하는 k 값은 1, 2, 5, 10입니다. 실제로 이 값들로 배열의 각 요소를 나누면 나머지가 모두 같아지는 것을 확인할 수 있습니다.
접근 방법
배열 안의 두 값 x와 y(x > y)를 생각해 봅시다. 두 값의 나머지가 같으려면 다음 식이 성립해야 합니다.
(y + 차이) % k = y % k
이 식을 정리하면 다음과 같은 결론을 얻습니다.
차이 % k = 0
즉, 두 값의 차이가 k로 나누어떨어져야 한다는 의미입니다.
따라서 해결 절차는 다음과 같습니다.
1. 배열을 정렬하여 최댓값과 최솟값의 차이(diff)를 구합니다.
2. diff의 모든 약수를 구합니다.
3. 각 약수에 대해 배열의 모든 요소를 나눴을 때 나머지가 동일한지 검사하고, 조건을 만족하는 값을 출력합니다.
예제 코드
#include<bits/stdc++.h>
using namespace std;
int equal_modulus (int arr[], int len) {
sort(arr, arr + len);
int diff = arr[len-1] - arr[0];
// 모든 약수를 저장할 벡터
vector <int> divi;
for (int i = 1; i*i <= diff; i++) {
if (diff%i == 0) {
divi.push_back(i);
if (i != diff/i)
divi.push_back(diff/i);
}
}
// 모든 요소에 대해 나머지가 같은지 검사
for (int i = 0; i < divi.size(); i++) {
int temp = arr[0]%divi[i];
int j;
for (j = 1; j < len; j++)
if (arr[j] % divi[i] != temp)
break;
// 조건을 만족하는 k 값 출력
if (j == len)
cout << divi[i] <<" ";
}
return 0;
}
int main() {
int arr[] = {12, 22, 32};
int len = sizeof(arr)/sizeof(arr[0]);
cout << "The values of K :" << endl;
equal_modulus(arr, len);
return 0;
}실행 결과
The values of K : 1 2 10 5
코드 설명 및 복잡도
위 코드에서 약수를 구하는 부분은 1부터 √diff까지만 반복하면서 i와 diff/i를 함께 저장하는 방식을 사용합니다. 이를 통해 약수를 O(√diff) 시간 안에 효율적으로 구할 수 있습니다.
이후 각 약수마다 배열 전체를 순회하며 나머지가 일치하는지 확인하므로, 전체 시간 복잡도는 O(d × n)입니다. 여기서 d는 diff의 약수 개수, n은 배열의 크기입니다.
참고로 배열의 모든 요소가 동일한 경우 diff가 0이 되는데, 이때는 어떤 양의 정수 k를 선택해도 나머지가 항상 0으로 같으므로 별도 처리가 필요할 수 있습니다.