프로그래머스 - 유한소수 판별 - C++

https://school.programmers.co.kr/learn/courses/30/lessons/120878

프로그래머스

 

#include <string>
#include <vector>

using namespace std;

int solution(int a, int b) {
    int answer = 0;
    int coa = a;
    int cob = b;
    // 기약분수로 바꾸기
    for (int i = a; i >= 2; i--)
    {
        if (coa % i == 0 && cob % i == 0)
        {
            coa /= i;
            cob /= i;
        }
    }
    bool ansch = true;
    // 분모의 소인수찾기
    for (int i = 2; i <= cob; i++)//인수
    {
        bool ch = false;

        if (cob % i == 0)
        {
            for (int j = 2; j < i; j++)// 인수 중 소수인지?
            {
                if (i % j == 0)
                {
                    ch = true;
                    break;
                }
            }
            // false면 소인수임
            if (ch == false)
            {
                if (i != 2 && i != 5)
                    ansch = false;
            }
        }
    }
    if (ansch == true)return 1;
    else return 2;
}

 

설명

이 문제는 주어진 a, b에 대해서 a/b 분수가 유한소수인지를 판단하는 것이다.

유한소수인지 판단하는 근거는 a/b를 기약분수로 나타냈을 때, b의 소인수가 2,5로만 이루어져있는 것이다.

 

소인수란 소수인 인수라는 뜻이다.

 

문제를 푸는 순서는

1. a/b를 기약분수로 나타낸다.

2. b의 소인수를 찾아낸다.

3. 그 소인수 중 2와 5가 아닌 것이 있는지 확인한다. 

이다.

 

int coa = a;
    int cob = b;
    // 기약분수로 바꾸기
    for (int i = a; i >= 2; i--)
    {
        if (coa % i == 0 && cob % i == 0)
        {
            coa /= i;
            cob /= i;
        }
    }

변수 coa, cob 에 각각 a,b값을 넣어준다.  (원본 값 유지를 위함이다.)

 a부터 2까지 차례로 보며 a와 b가 동시에 나눠지는 수가 있는지 확인하며 계속 약분한다. 

그럼 기약분수의 분모,분자가 cob,coa가 된다. 

 

bool ansch = true;
    // 분모의 소인수찾기
    for (int i = 2; i <= cob; i++)//인수
    {
        bool ch = false;

        if (cob % i == 0)
        {
            for (int j = 2; j < i; j++)// 인수 중 소수인지?
            {
                if (i % j == 0)
                {
                    ch = true;
                    break;
                }
            }

그리고 분모의 소인수를 찾기위해 2부터 cob까지 for문으로 차례로 살펴본다. 

cob가 나눠지는 i 중에(인수 중에) 그 i가 소수인지를 j for문으로 2부터 i-1 까지 확인한다.

만약 나누어 떨어지는 수가 있다면 소수가 아닌 것이다. 

그래서 소수가 아니면 ch값은 true가 된다.

 

// false면 소인수임
            if (ch == false)
            {
                if (i != 2 && i != 5)
                    ansch = false;
            }

 따라서 ch값이 false면 i는 소인수라는 뜻이고 이 때, i가 2 또는 5인지를 확인하면 된다. 

여기서 ansch가 i for문 동안 true 값을 유지한다면 1을 리턴하면 된다.

만약 false값이라면 2를 리턴한다.