문제 개요
양의 정수로 이루어진 배열 nums가 주어졌다고 가정해 봅시다. 배열에서 몇 개의 원소를 골라 부분 집합을 만들고, 선택된 각 원소에 임의의 정수를 곱한 뒤 모두 더했을 때 그 합이 1이 될 수 있다면, 이 배열을 좋은 배열(good array)이라고 부릅니다. 우리가 할 일은 주어진 배열이 좋은 배열인지 아닌지를 판별하는 것입니다.
예를 들어 입력이 [12, 23, 7, 5]라면 결과는 True입니다. 5와 7을 선택해 5×3 + 7×(−2) = 1을 만들 수 있기 때문입니다.
접근 방법: 베주 항등식과 GCD
이 문제의 핵심은 베주 항등식(Bézout's identity)입니다. 베주 항등식에 따르면, 여러 정수의 최대공약수(GCD)가 d일 때 각 수에 적절한 정수를 곱해 더하면 반드시 d를 만들어낼 수 있습니다. 이를 문제에 적용하면 다음과 같습니다.
- 배열 전체의 GCD가 1이면 → 적절한 정수 계수의 조합으로 반드시 1을 만들 수 있으므로 좋은 배열입니다.
- GCD가 1보다 크면 → 어떤 조합의 합도 항상 그 GCD의 배수가 되므로 절대 1을 만들 수 없습니다.
따라서 배열의 모든 원소를 순회하며 최대공약수를 누적으로 계산한 뒤, 그 값이 1인지만 확인하면 됩니다.
알고리즘 단계
- g를 nums[0]으로 초기화합니다.
- i를 1부터 배열의 마지막 인덱스까지 증가시키며 다음을 반복합니다.
- g := gcd(g, nums[i])
- 반복이 끝난 후 g가 1이면 true를 반환하고, 그렇지 않으면 false를 반환합니다.
이 알고리즘의 시간 복잡도는 O(n · log(max(nums)))로 매우 효율적입니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int gcd(int a, int b){
return !b ? a : gcd(b, a % b);
}
bool isGoodArray(vector<int>& nums){
int g = nums[0];
for (int i = 1; i < nums.size(); i++)
g = gcd(g, nums[i]);
return g == 1;
&;}
};
main(){
Solution ob;
vector<int> v = {12,23,7,5};
cout << (ob.isGoodArray(v));
}
입력
{12,23,7,5}출력
1
출력이 1(true)이므로 배열 {12, 23, 7, 5}는 좋은 배열임을 확인할 수 있습니다.