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

 

 

 

위 그림처럼, 철수는 10과 20의 카드를 지니고 있고 영희는 5와 17의 카드를 지니고 있다고 가정해보자.

 

철수의 모든 카드는 1, 2, 5, 10 으로 나눌 수 있다.

영희의 모든 카드는 1, 5, 17로 나눌 수 있다.

 

이 때, 철수의 모든 카드는 나눌 수 있으면셔, 영희의 카드는 단 1개도 나눌 수 없는 수를 구하면 된다.

철수의 모든 카드를 나눌 수 있는 숫자중, 2와 10은 영희의 카드를 단 1개도 나눌 수 없다.

 

이 때, 2와 10중 더 큰 값인 10이 정답이 된다.

 

 

 

문제 풀이

---

 

이 문제는 최대공약수를 이용하면 간단하게 풀 수 있다.

 

철수가 가진 모든 숫자 카드를 나눌 수 있는 수는 쉽게 말해서 공약수이다.

 

어떤 정수 A를 정수 B로 나눌 수 있다면, B를 A의 약수라고 칭한다.

어떤 정수 A와 B를 C로 나눌 수 있다면, C는 A와 B의 공약수라고 칭한다. (공통된 약수)

 

이러한 정의를 따져보면, 모든 숫자 카드를 하나의 숫자로 나눌 수 있다면, 그 숫자는 모든 숫자 카드의 공약수인 것이다.

문제는 그러한 숫자들 중에서 가장 큰 값을 구하는 문제이기 때문에 최대 공약수를 구하면 된다.

 

최대 공약수는 어떻게 구할까?

유클리드 호제법이라는 알고리즘을 사용하면 된다.

 

모른다면, 아래 링크를 참고하도록 하자.

알고리즘 - 유클리드 호제법 (두 수의 최대 공약수 구하기) (tistory.com)

알고리즘 - 유클리드 호제법 (두 수의 최대 공약수 구하기)

 

이제 1명의 카드를 모두 나눌 수 있는 숫자는 구했으니, 그 숫자가 다른 1명의 카드를 나눌 수 있는가를 검사하면 끝이다.

간단하게, 반복문을 돌며 나누기 연산 혹은 나머지 연산을 하면 끝이다.

 

1. 철수의 모든 카드는 나눌 수 있으나 영희의 카드는 단 1개도 나눌 수 없는 숫자

2. 영희의 모든 카드는 나눌 수 있으나 철수의 카드는 단 1개도 나눌 수 없는 숫자

 

두 경우의 숫자를 구한 뒤, 둘 중 더 큰 값을 return하면 된다.

 

 

 

풀이 코드

---

int Answer_1 = 0;
int Answer_2 = 0;

 

먼저, 2개의 int형 변수를 선언하였다.

 

문제에선 2개의 경우가 나온다.

 

1. 철수의 모든 카드는 나눌 수 있으나 영희의 카드는 단 1개도 나눌 수 없는 숫자

2. 영희의 모든 카드는 나눌 수 있으나 철수의 카드는 단 1개도 나눌 수 없는 숫자

 

두 경우에 대한 숫자를 구한 뒤, 둘 중 최대값으로 반환할 것이기 때문에 2개의 변수를 선언한 것이다.

 

int GetGCD(int _A, int _B)
{
    int Remain = 0;
    while (_B > 0)
    {
        Remain = _A % _B;
        _A = _B;
        _B = Remain;
    }

    return _A;
}

위는 최대 공약수를 구하는 유클리드 호제법에 대한 코드이다.

 

int GCD_A = arrayA[0];
for (int i = 1; i < arrayA.size(); i++)
{
    GCD_A = GetGCD(GCD_A, arrayA[i]);
}

 

유클리드 호제법을 이용하여, 철수가 가진 모든 숫자의 공약수를 구해주었다.

(위와 같이 반복문을 이용하면 모든 원소에 대한 최대공약수를 구할 수 있다.)

 

Answer_1 = GCD_A;
for (int i = 0; i < arrayB.size(); i++)
{
    int Remain = arrayB[i] % GCD_A;

    if (Remain == 0)
    {
        Answer_1 = 0;
        break;
    }
}

 

이후, Answer_1엔 일단 최대 공약수를 넣어 주었다.

이 값으로 영희가 가진 숫자중 나누어지는 숫자가 단 1개도 없다면, 이 값을 답으로 픽스하면 되고

1개라도 나누어지는 숫자가 있다면, 값을 0으로 바꿔준 뒤 break해주면 된다.

 

{
    int GCD_B = arrayB[0];
    for (int i = 1; i < arrayB.size(); i++)
    {
        GCD_B = GetGCD(GCD_B, arrayB[i]);
    }

    Answer_2 = GCD_B;
    for (int i = 0; i < arrayA.size(); i++)
    {
        int Remain = arrayA[i] % GCD_B;

        if (Remain == 0)
        {
            Answer_2 = 0;
            break;
        }
    }
}

 

Answer_2는 영희와 철수만 바뀌었을 뿐 완전히 동일하게 계산하였다.

return std::max(Answer_1, Answer_2);

 

마지막으로 두 값중 최대값을 리턴하면 끝이다.