tjftkddnjs   1년 전

While문에서 1과 45000의 최소공배수를 구하는 경우같이 큰 값을 계산할때는 x +=1 이 들어간 while문이 45000회 실행되면서 시간초과가 일어난것같습니다.

while문을 적게 실행 될 수 있을만한 아이디어가 있을까요??

0000000000   1년 전

컴퓨터는 연산을 겨우 45000회 하는 걸로는 끄떡없습니다. 5행의 while문 조건이 잘못된 것 같네요.

pielo   1년 전

최대공약수를 먼저 구한 후 이를 활용하여 최소공배수를 구하는 방법이 있습니다.

최대공약수를 빠르게 구하는 법은 Euclidean algorithm(유클리드 호제법)을 참고하세요.

tjftkddnjs   1년 전

0000000000pielo 유클리드 호제법으로 풀었습니다. 다들 도움주셔서 감사합니다! 추가로 5행의 while문에서 어떤걸 고쳐야 하는지는 아직도 잘 모르겠습니다.. 

0000000000   1년 전

5행은 제가 졸려서 잘못 생각했던 것 같네요. 위 코드상에서는 44999 45000이 입력으로 들어왔을 때 시간초과가 납니다.

사실 굳이 호제법을 쓰지 않고 선형 시간으로 GCD를 구한 뒤 그걸로 LCM을 구해도 됩니다.

tjftkddnjs   1년 전

0000000000 자료구조, 알고리즘을 아직 보지않은 상태라서 찾아봐야겠네요 감사합니다

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