[프로그래머스 / C++] 유한소수 판별하기

문제

유한소수 판별하기 : 문제 링크

문제 분석

• 두 정수 a와 b가 매개변수로 주어질 때, a/b가 유한소수이면 1을, 무한소수라면 2를 return

  유한소수 : 소수점 아래 숫자가 계속되지 않고 유한개인 소수, 기약분수로 나타내었을 때, 분모의 소인수가 2와 5만 존재해야한다.

• gcd() 함수로 매개변수 a,b의 최대공약수를 구하고, 분모를 최대공약수로 나눈값을 저장. while loop에서 분모가 2 또는 5로 나눠질 경우, 그 값으로 나눈 값을 분모에 저장하고, 더 이상 연산할것이 없다면 탈출.
• 최종적으로 나온 분모값이 1이라면 유한소수 이므로 1을, 이외의 값이라면 무한소수 이므로 2를 return

풀이

#include <vector>

using namespace std;

int gcd(int a, int b) {
    return (a % b == 0 ? b : gcd(b, a % b));
}

int solution(int a, int b) {
    b /= gcd(a, b);
    
    while(1) {
        if(b % 2 == 0) b /= 2;
        else if(b % 5 == 0) b /= 5;
        else break;
    }
    if(b == 1) return 1;
    else return 2;
}