Level 2. 숫자 카드 나누기

Level 2. 숫자 카드 나누기

 

 

우선, 원소의 범위가 크므로 단순 반복문을 사용하면 시간 초과가 발생할 것이다.

 

약수를 구하는 것은 유클리드 호제법을 사용하면 된다.

• GCD(a, b) = GCD(b, (a % b))
• a, b의 대소관계는 상관 없다.

 

GCD(a, b, c) = GCD(GCD((a, b), c)이다.

 

이 문제는 그냥 각 배열의 최대공약수를 구하고, 조건에 맞는 큰 수를 반환하면 된다.

• 문제에서는 마치 최대 공약수를 구하고도, 그 최대 공약수의 약수 중에서 조건에 맞는 것을 찾아야 하는 것처럼 나와 있다.
• 하지만, 최대 공약수로 나누어 떨어지는 데 그 약수로 나누어 떨어지지 않는 경우는 존재할 수 없다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int GCD(int a, int b)
{
    return b ? GCD(b, a % b) : a;
}

int max_divisor(vector<int> array1, vector<int> array2)
{
    int gcd = array1[0];

    for (int e : array1)
        gcd = GCD(gcd, e);

    for (int e : array2)
        if (e % gcd == 0)
            return 0;

    return gcd;
}

int solution(vector<int> arrayA, vector<int> arrayB)
{
    int divA = max_divisor(arrayA, arrayB);
    int divB = max_divisor(arrayB, arrayA);

    return max(divA, divB);
}