[백준][C++] 1934 최소공배수

1934. 최소공배수

1934번: 최소공배수

문제 풀이

GitHub - minyoung529/AlgorithmStudy: 여러 알고리즘 문제를 푸는 저장소입니다.

 

다른 GDC 문제를 응용... (복붙)해서 풀어야지! 라고 생각했던 문제지만, 보기 좋게 시간 초과가 났다.

 

a부터 a * b까지 계속 돌리는 방식이다 보니... 어쩌면 시간 초과가 날 수밖에 없었다.

그래서 아래 공식을 이용하기로 했다!

LCM(a,b) = a*b / GCD(a, b)

그리고 GCD(최대공약수)를 구하기 위한 최적의 방법은 유클리드 호제법이라고 생각했기 때문에...

GDC를 구할 수 있는 알고리즘이다. 즉,

GCD(a, b) == GCD(b, a%b)

인 것!

 

재귀함수를 이용해서 풀 수 있었지만, 재귀보다 while문이 좋을 거라고 판단해 while문으로 GCD를 구했다.

while (b != 0)
{
    int r = a % b;
    a = b;
    b = r;
}
// a == GCD(a,b)

그리고 성공! 유클리드 호제법에 대해서 처음 알게된 문제였고, 꽤 효율적이라고 생각하게 한 문제였다.