숫자 카드 나누기

문제 위치 : https://school.programmers.co.kr/learn/courses/30/lessons/135807

프로그래머스

 

최대공약수를 응용하는 문제이다.

한 배열은 모두 나눌 수 있으며 상대 배열은 나눌 수 없어야 하므로 최대공약수를 구해 상대 배열을 나눌 수 있는지 여부를 확인해 주면 된다.

 

이를 위해 두 수의 최대공약수를 구하는 함수와 그 함수를 이용하여 여러 수의 최대공약수를 구하는 함수를 구현하였다.

 

이후 해당 값들이 조건에 맞는지 확인하여 반환하도록 하였다.

#include <string>
#include <vector>
using namespace std;

int gcd(const int& A,const int& B){
	if(B==0)
		return A;
	return gcd(B,A%B);
}

int GCD(const vector<int>& array){
	int pre = array[0];
    for(int a : array){
        pre = gcd(pre,a);
    }
    return pre;
}

int solution(vector<int> arrayA, vector<int> arrayB) {
    int answer = 0;
    vector<int> ans(2,0);
    int ans_A = GCD(arrayA), ans_B = GCD(arrayB);
    ans[0] = ans_A;
    for(int b : arrayB){
        if(b%ans_A==0){
            ans[0] = 0;
            break;
        }
    }
    ans[1] = ans_B;
    for(int a : arrayA){
        if(a%ans_B==0){
            ans[1] = 0;
            break;
        }
    }
    for(int i : ans){
        if(answer<i) answer = i;
    }
    return answer;
}