yoonsh0715   1년 전

틀렸다고 나오는데 그 이유를 몰라 질문 드립니다. 혹시 반복문에 따른 조건 시간보다 오래 걸려서 그러는 건가요?

js7777   1년 전

입력값으로

1 1

이 주어지는 경우를 생각해보면 좋을 것 같습니다.

처음 while문에서 i--때문에 i가 0이 된 상태로 나머지연산을 하게 됩니다.

not_strober   1년 전

1. 최소 공약수를 찾는 부분은 문제가 없습니다. 비록 유클리드 호제법이라는 훨씬 성능 좋은 방법이 있긴 하지만 입력 10,000 이하에 대해서는 완전 탐색도 큰 문제가 아닙니다.

2. 그러나 최소 공배수를 찾는 곳에서, x = 9,999, y = 10,000일 때를 가정해 보면 둘은 서로소이므로 반복이 거의 1억 번 가까이 일어납니다.

3. 모듈로 연산은 느립니다. 그걸 반복마다 두 번씩 하고 있습니다.

4. 상기의 이유로 이 코드는 시간 초과를 받습니다.

최대 공약수를 찾았다면, 최대 공약수와 최소 공배수의 정의를 이용해 최소 공배수를 곧바로 구할 수 있습니다.

sianke1991   1년 전

while 조건으로 사용된 i++, i-- 연산이

반복문보다 먼저 수행되는 것 같습니다.

not_strober   1년 전

@js7777 그 말씀이 맞네요. 여기도 문제가 있네요.

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