[백준 1735] 분수 합 (Java)

문제

 

코드

참고

입력되는 네 자연수는 모두 30,000 이하의 조건을 가지고 있다.

만약 최악의 조건으로 두 분수의 분모 모두 30,000 일 경우, 시간 초과를 피할 수 없다.

즉, 일반적인 소인수 분해로는 시간복잡도는 O(N) 으로 시간초과가 나온다.

 

유클리드 호제법를 이용하여, 시간복잡도는 O(logN)을 만들어야 가능한 문제이다.

 

유클리드 호제법에 대한 자세한 설명을 위해 링크를 걸어 두겠다.

 

참고 바랍니다.