les951   3년 전

바로 분모끼리 통분한 다음 최대공약수로 나누어 주었습니다.

혹시 최대공약수를 직접 구하는 과정에서 시간초과가 나는 거 같은데, for 문에서 최대 3만번 연산하고 if에서 3만번 연산하니까 

총 900,000,000번 연산이 되어서 시간초과가 나는 거 맞나요?

그러면 이 문제 같은 경우에는 이중 구문은 쓰지 않고 해결해야 하는 건가요?

sunghyeck17   3년 전

for 문이 최대 9억번 반복될 수 있습니다. (if문은 한번 반복마다 2번만 실행됩니다)

최대공약수를 구하는 과정에서 2부터 최대 9억까지의 수를 전부 나눠보기 때문에 시간초과가 발생합니다.

더 빠르게 구하는 방법으로 유클리드 호제법이 있습니다. 유용하고 쉬운 테크닉이니 한번 읽어보세요.

les951   3년 전

감사합니다!

댓글을 작성하려면 로그인해야 합니다.