문제 개요
이 튜토리얼에서는 배열의 최대공약수(GCD)가 1이 되도록 배열을 변환하는 프로그램을 작성하는 방법을 알아봅니다.
정수 배열과 양의 정수 k가 주어집니다. 사용할 수 있는 연산은 오직 하나, 즉 배열의 원소를 k 이하의 값으로 나누는 것이며, 이 연산을 필요한 만큼 반복할 수 있습니다. 목표는 모든 원소의 GCD를 정확히 1로 만드는 것입니다.
접근 방법
이 문제의 핵심은 배열 전체의 GCD에 주목하는 것입니다. 원소를 나누는 연산은 결국 공통 약수를 제거하는 작업이므로, 초기 GCD의 모든 소인수가 k 이하라면 GCD를 1로 만들 수 있습니다.
- 먼저 배열 전체의 GCD를 계산합니다.
- GCD를 소인수분해하여 가장 큰 소인수를 찾습니다.
- 가장 큰 소인수가 k 이하라면 "Yes", 그보다 크다면 "No"를 반환합니다.
예를 들어 배열이 {10, 15, 30}이고 k가 6이라고 가정해 보겠습니다. 배열의 GCD는 5이고, 5의 가장 큰 소인수는 5입니다. 5는 6 이하이므로 각 원소를 적절히 나누어 GCD를 1로 만들 수 있습니다.
구현 예시
#include <bits/stdc++.h>
using namespace std;
// 배열의 GCD를 계산하는 함수
int calculate_gcd(int* arr, int n){
int gcd = arr[0];
for (int i = 1; i < n; i++)
gcd = __gcd(arr[i], gcd);
return gcd;
}
// 연산으로 GCD를 1로 만들 수 있는지 확인하는 함수
bool convertGcd(int* arr, int n, int k){
int gcd = calculate_gcd(arr, n);
int max_prime = 1;
for (int i = 2; i <= sqrt(gcd); i++) {
while (gcd % i == 0) {
gcd /= i;
max_prime = max(max_prime, i);
}
}
max_prime = max(max_prime, gcd);
return (max_prime <= k);
}
int main(){
int arr[] = { 10, 15, 30 };
int k = 6;
int n = sizeof(arr) / sizeof(arr[0]);
if (convertGcd(arr, n, k) == true)
cout << "Yes";
else
cout << "No";
return 0;
}
실행 결과
Yes
코드 설명
calculate_gcd 함수는 유클리드 호제법을 이용해 배열의 모든 원소에 대한 GCD를 순차적으로 계산합니다.
convertGcd 함수는 계산된 GCD를 2부터 √GCD까지의 수로 나누어 소인수분해를 수행하고, 그 과정에서 발견되는 가장 큰 소인수를 추적합니다. 마지막에 남은 값 역시 소수일 수 있으므로 함께 비교한 뒤, 가장 큰 소인수가 k 이하인지 검사합니다.
위 예제에서 GCD는 5이고 가장 큰 소인수 5가 k(6) 이하이므로 프로그램은 "Yes"를 출력합니다.
시간 복잡도
GCD 계산에는 O(n log M)(M은 원소의 최댓값), 소인수분해에는 O(√GCD)가 소요되므로 전체 시간 복잡도는 O(n log M + √GCD)입니다.