[C++] Programmers | 숫자 카드 나누기

숫자 카드 나누기

프로그래머스

---

✍🏻 풀이

이 문제는 N개의 최소공배수 문제와 조금 비슷한 문제였다.

[C++] Programmers | N개의 최소공배수

1. A배열, B배열의 최대공약수인 A_GCD, B_GCD를 각각 구해준다 (유클리드 호제법 이용)
2. A배열을 순회하며 B_GCD로 나누어 떨어지는 경우가 있으면 답이 될 수 없으므로 A_flag에 0을 저장하고 반복문을 종료한다.
   A배열의 원소가 전부 B_GCD로 나누어 떨어지지 않는다면 A_flag에 B_GCD를 저장한다.
3. B배열도 2번과 마찬가지로 처리한다.
4. A_flag와 B_flag 중 더 큰 값을 return한다.

---

✅ Accept Code

// programmers week6-4
// 숫자 카드 나누기

#include <bits/stdc++.h>

using namespace std;

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

int solution(vector<int> arrayA, vector<int> arrayB) {
    int A_GCD = arrayA[0], B_GCD = arrayB[0];
    for (int i = 1; i < arrayA.size(); i++) {
        A_GCD = GCD(A_GCD, arrayA[i]);
        B_GCD = GCD(B_GCD, arrayB[i]);
    }

    int A_flag = 0, B_flag = 0;

    for (int i = 0; i < arrayA.size(); i++) {
        if (arrayA[i] % B_GCD != 0) A_flag = B_GCD;
        else {
            A_flag = 0;
            break;
        }
    }

    for (int i = 0; i < arrayB.size(); i++) {
        if (arrayB[i] % A_GCD != 0) B_flag = A_GCD;
        else {
            B_flag = 0;
            break;
        }
    }

    return max(A_flag, B_flag);
}