[ C++ ] Code-Up 1565: 함수로 최소공배수 리턴하기

 

안녕하세요? 수구리입니다.

 

오늘은 배수 관련되어서 문제를 다뤄보려고 합니다.

 

문제 확인은 아래 링크에 있습니다~

 

[ 문제 ] 1565. 함수로 최소공배수 리턴하기

[기초-함수작성] 함수로 최소공배수 리턴하기

 

 

[ 나의 풀이 ]

#include <stdio.h>

int gcd(int p, int q){ if(p==0) return q; return gcd(q%p, p);}

unsigned long long lcm(auto x, auto y){
    unsigned long long R1 = x / gcd(x, y);
    unsigned long long R2 = y / gcd(x, y);
    
    unsigned long long lcm = gcd(x,y) * R1 * R2;
    
    return lcm;
}
int main()
{
  int a, b;
  scanf("%d%d", &a, &b);
  printf("%lld\n", lcm(a, b));
}

 

 

[ 설명 ]

문제에서 요구하는 것은 lcm 함수를 작성하는 것입니다.

 

1. 두 자연수 a, b를 입력받습니다.

2. a, b를 인자로 하는 lcm 함수를 호출

3. 최소공배수를 구하기 위해서는 두 수의 최대공약수를 주어진 gcd 함수를 통해서 구하고,

4. 최대 공약수로 두 자연수를 나눈 몫(R1, R2)을 구해줍니다.

5. R1 * R2 * 두 수의 최대공약수가 리턴값입니다.

 

[ 참고 ]

#include <numeric> // c++ 17 -> gcd & lcm 제공

C++ 17부터는 두 수의 gcd (최대공약수)와 lcm (최소공배수)에 대한 라이브러리가 제공되어 진다고 합니다.