백준알고리즘 #1934 최소공배수 Java

백준알고리즘 #1934 최소공배수 문제

 

주어진 a와 b값의 최소공배수를 구하는 문제이다.

최소공배수는 a와 b의 공배수 중 가장 작은 수이므로 단순히 두 수중 큰 수부터 시작하여 하나씩 비교하는 방식으로 쉽게 구할 수 있다.

 

시간 초과 코드

위와 같이 먼저 a와 b의 값을 비교하여 큰 수를 b쪽에 두고, while문을 이용하여 b값을 시작값으로 두고 1씩 증가시키면서 조건(공배수)을 만족시키는 값을 찾을 수 있다.

다만 이렇게 구하게 되면 시간이 굉장히 오래걸리기 때문에 위와 같은 코드로 제출하게 되면 시간 초과라는 오류가 발생하게 된다.

따라서 조금 다른 방식으로 구해보았다.

정답 코드

최소공배수는 두 수의 곱 / 최대공약수 로 구할 수 있기 때문에 먼저 최대공약수를 구한다.

최대공약수는 1부터 두 수중 작은 수까지로 한정되어 있기 때문에 비교적 짧은 시간에 값을 구할 수 있다.

구한 최대공약수를 두 수의 곱에 나누어주면 우리가 원하는 값인 최소공배수를 얻을 수 있다.