1250. Check If It Is a Good Array - Streak 5

 

이 문제는 결국 양수와 음수의 조합으로 나타내진다.
이를 모듈러 연산으로 나타낼 수 없을까?

 

여기서 확장 유클리드 호제법이 적용 가능해진다.

gcd = 1인 조합이 하나라도 있으면 True이다.
근데 우리 문제는, 다음과 같은 형태이다.

이걸 확장 유클리드 호제법의 형태로 바꿀 수 없을까?
둘을 더하면, 최대공약수는 약수로 남기고, 나머지는 더한 효과가 된다.

즉, 둘을 더해도 최대공약수는 무조건 남는다

 

최대공약수는 이 문제에서 지워야 하는 대상이므로,
전체의 최대공약수가 1이면 True이고, 전체의 최대공약수가 1이 아니면 False이다.

class Solution {
    public boolean isGoodArray(int[] nums) {
        int now = nums[0];
        for(int i = 1; i<nums.length; i++){
            now = gcd(now, nums[i]);
        }
        return now==1;
    }

    private int gcd(int a, int b){
        if(b==0){
            return a;
        }
        return gcd(b, a%b);
    }
}