thnam91   7년 전

파이썬으로 짜서 속도가 문제가 되는 건지 모르겠습니다.

혹시 코드상에서 속도를 올릴 수 있는 부분이 있을까요?

소인수분해를 위한 함수와 GCD를 구하기 위한 함수를 이전 문제들 풀기 위해서 작성했습니다.

이전 문제들은 앞서 언급한 함수를 가지고 해결했기에 성능은 보장되었다고 생각하여 이번 문제에도 재사용하려고 합니다.


그런데 시간초과가 뜨는데 어디에서 해결해야할 지 모르겠습니다.

plzrun   7년 전

최대공약수는 유클리드 호제법을 써서 구해야 합니다.

인터넷에 많이 있으니 그걸 찾아보세요.

위의 최대공약수 구현방법은 너무 느립니다.


아래 소스는 AC받은 python3 코드입니다.

thnam91   7년 전

감사합니다 유클리드 호제법에 대해서 알아보고 다시 짜봐야 겠습니다!

thnam91   7년 전

감사합니다. 이제 시간이 나서 풀었는데 제가 구한 방법보다 유클리드 호제법을 활용한 것이 빠르기도 빠르고, 구현도 훨씬 쉽네요.

덕분에 하나 더 배워갑니다!

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