[프로그래머스] Lv.0 유한소수 판별하기 c++

 

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

프로그래머스

 

소수점 아래 숫자가 계속되지 않고 유한개인 소수를 유한소수라고 합니다. 

분수를 소수로 고칠 때 유한소수로 나타낼 수 있는 분수인지 판별하려고 할 때,

두 정수 a와 b가 주어질 경우 a/b가 유한소수면 1을, 무한소수면 2를 return 해주세요.

 

조건

• 기약분수로 나타내었을 때, 분모의 소인수가 2와 5만 존재해야 합니다.

 

풀이 방법

#include <numeric>의 gcd(a, b) 함수를 사용하면 됩니다.
두 변수 a와 b의 최대공약수를 구해주기 때문에 계산이 간단해집니다.
먼저 두 매개변수의 최대공약수를 구한 뒤, 분모 b를 그 값으로 나눕니다.
그다음, 분모 b의 소인수가 2와 5로만 구성되어야 하므로 b를 더 이상 나누어지지 않을 때까지 2와 5로 나눕니다. 
이 과정을 통해 b가 1이 되면 유한소수, 그렇지 않으면 무한소수로 판단할 수 있습니다.

 

아래 gcd()함수에 대한 간단한 예제도 첨부하겠습니다.

#include <iostream>
#include <numeric>

using namespace std;

int main() {
    int a = 48, b = 18;

    int gcd_ab = gcd(a, b);

    cout << "두 수 " << a << "와 " << b << "의 최대공약수는 " << gcd_ab << "입니다." << endl;

    return 0;
}

//두 수 48와 18의 최대공약수는 6입니다.

 

풀이 코드

#include <string>
#include <vector>
#include <numeric>

using namespace std;

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