문제 개요
크기가 n인 배열이 주어졌을 때, 배열의 모든 요소를 동일한 값으로 만든 후 얻을 수 있는 최대 합을 구하는 것이 목표입니다. 단, 허용되는 연산은 하나뿐입니다. 임의의 두 요소를 선택하고, 그중 더 큰 값을 두 수의 절대 차(차이)로 대체하는 것입니다.
예를 들어 배열이 [9, 12, 3, 6]이라면 결과는 12가 됩니다. 과정을 단계별로 살펴보겠습니다.
- A[1]을 A[1] – A[3] = 12 – 6 = 6으로 교체 → [9, 6, 3, 6]
- A[3]을 A[3] – A[2] = 6 – 3 = 3으로 교체 → [9, 6, 3, 3]
- A[0]을 A[0] – A[1] = 9 – 6 = 3으로 교체 → [3, 6, 3, 3]
- A[1]을 A[1] – A[3] = 6 – 3 = 3으로 교체 → [3, 3, 3, 3]
이제 모든 요소가 3으로 동일해졌으며, 합은 3 × 4 = 12입니다.
접근 방식: 최대공약수(GCD) 활용
허용된 연산을 수식으로 표현하면 A[i] = A[i] – A[j] (단, A[i] > A[j]) 형태입니다. 즉, 두 수를 골라 큰 값을 두 수의 절대 차로 바꾸는 작업을 모든 요소가 같아질 때까지 반복하는 것입니다.
여기서 중요한 통찰은 이 과정이 유클리드 호제법(Euclidean Algorithm)과 정확히 같은 원리라는 점입니다. 두 수에 이 연산을 반복해서 적용하면 결국 두 수의 최대공약수(GCD)에 도달합니다. 마찬가지로 배열 전체에 이 연산을 계속 적용하면 모든 요소는 배열 전체의 최대공약수로 수렴하게 됩니다.
또한 연산 도중 어떤 요소의 값도 항상 전체 GCD의 배수로 유지되므로, 최종 공통 값으로 만들 수 있는 최댓값은 GCD 그 자체입니다. 따라서 최대 합은 다음과 같이 간단히 계산됩니다.
최대 합 = GCD(arr[0], arr[1], ..., arr[n-1]) × n
C++ 구현 예제
#include<iostream>
#include<algorithm>
using namespace std;
// 배열 전체의 최대공약수(GCD)를 구하는 함수
int findSameElement(int arr[], int n) {
int gcd_val = arr[0];
for (int i = 1; i < n; i++)
gcd_val = __gcd(arr[i], gcd_val);
return gcd_val;
}
// 최대 합 = GCD × 요소 개수
int getMaxSum(int arr[], int n) {
int value = findSameElement(arr, n);
return (value * n);
}
int main() {
int arr[] = {3, 9, 6, 6};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "The maximum sum is: " << getMaxSum(arr, n);
}실행 결과
The maximum sum is: 12
배열 {3, 9, 6, 6}의 최대공약수는 3이므로, 최대 합은 3 × 4 = 12가 출력됩니다. 이 방법의 시간 복잡도는 각 요소마다 GCD를 계산하므로 약 O(n log M)입니다(M은 배열 내 최댓값). 실제로 연산을 하나하나 시뮬레이션하는 것보다 훨씬 효율적입니다.