이 문제에서는 정수 n개로 이루어진 집합 arr[n]이 주어지며, 이 집합에 추가할 수 있는 최대 차이 요소의 개수를 구하는 것이 목표입니다. 여기서 '차이'란 |a-b| 형태를 의미하며, a와 b는 모두 집합에 속한 원소여야 합니다. 즉, 집합 내 원소들로 만들 수 있는 서로 다른 차잇값들을 계속 집합에 추가한다고 할 때, 최종적으로 몇 개의 새로운 요소를 더 넣을 수 있는지 세는 문제입니다. 예제를 통해 문제와 해결 방법을 자세히 살펴보겠습니다.
입력 − set = {1, 5}
출력 − 집합에 추가할 수 있는 최대 차이 요소의 개수: 1
설명 − 이 집합에는 차잇값이 하나뿐입니다. 즉, |1-5| = 4 입니다.
입력 − set = {2, 7, 1, 9}
출력 − 집합에 추가할 수 있는 최대 차이 요소의 개수: 5
설명 − 집합에서 만들 수 있는 차잇값들은 다음과 같습니다 −
|2-7| = 5
|7-1| = 6
|1-9| = 8
|2-9| = 7
|7-9| = 2
프로그램에서 사용된 접근 방식
집합의 값을 저장할 정수 배열 arr[n]을 준비합니다.
maximum() 함수 안에서 아래 3~6단계를 순서대로 수행합니다.
ele, temp, val 변수를 선언하고 모두 arr[0]으로 초기화합니다.
i를 1부터 배열의 크기까지 1씩 증가시키며 반복합니다.
배열의 모든 요소에 대한 최대공약수(gcd)를 구해 val에 누적합니다.
temp를 temp와 arr[i] 중 더 큰 값으로 갱신하여 배열의 최댓값을 찾습니다.
total을 temp/val(최댓값 ÷ 최대공약수)로 설정하고, max를 total에서 size(원래 집합의 크기)를 뺀 값으로 설정합니다.
max를 반환하고 결과를 출력합니다.
핵심 아이디어
이 접근 방식이 성립하는 이유는 다음과 같습니다. 집합에 차잇값을 계속해서 추가하면, 최종적으로 집합은 공차가 전체 원소의 최대공약수(gcd)인 등차수열 형태가 됩니다. 따라서 최종 집합에는 최대공약수부터 최댓값까지의 요소들이 포함되며, 전체 요소의 개수는 '최댓값 / 최대공약수'가 됩니다. 여기서 원래 집합의 크기를 빼면, 추가로 삽입할 수 있는 요소의 개수, 즉 최대 차이 요소의 개수를 구할 수 있습니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
// 최대 차이 요소를 구하는 함수
int maximum(int arr[], int size){
int ele = arr[0];
int val = ele;
int temp = ele;
for (int i = 1; i < size; i++){
val = __gcd(val, arr[i]);
temp = max(temp, arr[i]);
}
int total = temp / val;
int max = total - size;
return max;
}
int main(){
int arr[] = { 2, 7, 1, 9};
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"집합에 추가할 수 있는 최대 차이 요소의 개수: "<<maximum(arr, size);
return 0;
}
출력 결과
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다 −
집합에 추가할 수 있는 최대 차이 요소의 개수: 5
참고로 코드에 사용된 __gcd() 함수는 bits/stdc++.h 헤더에 포함되어 있으며, 두 정수의 최대공약수를 빠르게 계산해 주는 GCC 내장 함수입니다. 이처럼 최대공약수와 최댓값만을 이용하면 모든 차잇값을 일일이 계산하지 않고도 O(n) 시간 복잡도로 답을 구할 수 있어 매우 효율적입니다.