프로그래머스 숫자 카드 나누기 (c++)

최대공약수를 구하는 유클리드 호제법을 이용한 문제이다. 이에 최대공약수를 구하는 규칙을 모른다면 문제를 못푼다.

알고리즘 풀이

우리가 아는 유클리드 호제법은 두 수에 대한 최대공약수를 구하는 함수를 알고 있을 것이다.

그러나 이번 문제에서는 여러 수의 최대공약수를 구해야하는 문제이다. 그러면 어떻게 할까?

 

-> 생각보다 쉽다. 5개의 수가 있다고 할 때, 1번째 2번째 수의 최대공약수를 N이라 할 때, 3번째 수와 N의 최대공약수를 구하면 된다.

어짜피 첫번째, 두번째 수를 0으로 만들 수 있는 최대의 값이 N이기 때문에, N과 3번째수만 비교해도 3개의 수의 최대공약수를 알 수 있다. 

 

해당 방법으로 두 사람이 가진 카드뭉치의 최대공약수 2개를 구한 뒤, 상대방의 카드뭉치를 나눌 수 있는지 없는지 확인하면 된다.

int gcd(int a, int b) {
    int temp;
    while(b != 0) {
        temp = a % b;
        a = b;
        b = temp;
    }

    return a;
}

int solution(vector<int> arrayA, vector<int> arrayB) {
    int answer = 0;
    int resultA = arrayA[0], resultB = arrayB[0];

    for(int i=1; i<arrayA.size(); i++) {
        resultA = gcd(resultA, arrayA[i]);
        resultB = gcd(resultB, arrayB[i]);
    }

    bool validA = true, validB = true;

    for(int i=0; i<arrayA.size(); i++) {
        if(arrayB[i] % resultA == 0) {
            validA = false;
        }
        if(arrayA[i] % resultB == 0) {
            validB = false;
        }
    }

    if(validA) answer = max(answer, resultA);
    if(validB) answer = max(answer, resultB);

    return answer;
}