문제 코드 참고 입력되는 네 자연수는 모두 30,000 이하의 조건을 가지고 있다. 만약 최악의 조건으로 두 분수의 분모 모두 30,000 일 경우, 시간 초과를 피할 수 없다. 즉, 일반적인 소인수 분해로는 시간복잡도는 O(N) 으로 시간초과가 나온다. 유클리드 호제법를 이용하여, 시간복잡도는 O(logN)을 만들어야 가능한 문제이다. 유클리드 호제법에 대한 자세한 설명을 위해 링크를 걸어 두겠다. 참고 바랍니다.

유클리드 호제법이란? 2개의 자연수의 최대공약수를 구하는 알고리즘의 하나이다. 유클리드(Euclid)에 의해 기원전 300년경에 발견된 가장 오래된 알고리즘이다. (호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 말한다.) 유클리드 호제법을 알아보기 전, 어렸을적 배운 최대 공약수와 최소 공배수를 구하는 방법을 살펴보자. 소인수 분해를 이용해 최대 공약수, 최소 공배수 구하기 (중요x) 최대공약수 (Greatest Common Divisor) 두 자연수의 공통된 약수 중 가장 큰 수를 의미하며, GCD 라고 한다. 최소공배수 (Least Commn Multiple) 두 자연수의 공통된 배수 중 가장 작은 수를 의미하며, LCM 라고 한다. 소인수 분해를 이..

문제 코드

문제 코드

문제 코드

문제 코드 참고 백준에서 Java 사용 시, Pair 를 사용하면 컴파일 에러가 난다. Pair 와 같이 기능을 하는 java.util.AbstractMap.SimpleImmutableEntry 사용하자.