문제 설명
배열 A가 주어졌을 때, 요소들의 곱(product)과 최소공배수(LCM)가 서로 같은 부분 배열(subarray) 중 가장 긴 길이를 구하는 문제입니다. 만약 조건을 만족하는 부분 배열이 하나도 없다면 -1을 반환해야 합니다.
예를 들어 배열이 {6, 10, 21}이라고 해보겠습니다. 이때 부분 배열 {10, 21}을 살펴보면, 두 수의 LCM은 210이고 곱 역시 10 × 21 = 210으로 서로 일치합니다. 따라서 정답은 길이 2가 됩니다.
접근 방법
이 문제는 비교적 단순한 브루트 포스(완전 탐색) 방식으로 해결할 수 있습니다.
- 길이가 2 이상인 모든 가능한 부분 배열을 하나씩 검사합니다.
- 각 부분 배열에 대해 요소들의 LCM과 곱을 계산합니다.
- 두 값이 일치하면, 현재까지의 정답과 해당 부분 배열의 길이 중 더 큰 값으로 정답을 갱신합니다.
곱의 값이 빠르게 커질 수 있으므로 오버플로우를 방지하기 위해 long long 자료형을 사용하는 것이 좋습니다.
예제 코드
#include <iostream>
using namespace std;
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
int maxLengthLCMSubarray(int arr[], int n) {
int len = -1;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
long long lcm = 1LL * arr[i];
long long product = 1LL * arr[i];
for (int k = i + 1; k <= j; k++) {
lcm = (((arr[k] * lcm)) / (gcd(arr[k], lcm)));
product = product * arr[k];
}
if (lcm == product) {
len = max(len, j - i + 1);
}
}
}
return len;
}
int main() {
int arr[] = {8, 2, 6, 10, 13, 21, 7};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Maximum Length: " << maxLengthLCMSubarray(arr, n);
}출력 결과
Maximum Length: 3
코드 설명
- gcd 함수: 유클리드 호제법을 재귀적으로 사용하여 두 수의 최대공약수(GCD)를 구합니다. LCM은 '두 수의 곱 ÷ GCD' 공식으로 계산할 수 있으므로 필수적인 함수입니다.
- maxLengthLCMSubarray 함수: 시작 인덱스 i와 끝 인덱스 j를 이중 반복문으로 선택하여 모든 부분 배열을 생성합니다. 내부 반복문에서는 각 요소를 순회하며 LCM과 곱을 누적으로 계산한 뒤, 두 값이 같으면 정답을 갱신합니다.
- main 함수: 예제 배열 {8, 2, 6, 10, 13, 21, 7}에 대해 함수를 호출하고 결과를 출력합니다. 이 배열에서는 {10, 13, 21}처럼 서로소 관계인 세 수로 이루어진 부분 배열이 조건을 만족하므로 3이 출력됩니다.
시간 복잡도
시작점과 끝점을 선택하는 데 O(n²), 각 부분 배열마다 내부에서 다시 O(n)의 연산을 수행하므로 전체 시간 복잡도는 O(n³)입니다. 배열의 크기가 작거나 중간 정도일 때는 충분히 실용적이지만, 입력이 큰 경우에는 세그먼트 트리 등을 활용해 LCM 질의를 빠르게 처리하는 최적화 기법을 고려할 수 있습니다.