wjddydgns99   3년 전

처음 제출한 코드가 시간 초과가 나길래 우선 n=2일때만 시간초과 안나도록 수정했고, 밑에 코드는 n=2일때에만 국한되어서 시간초과 나지 않게 푼 소스거든요?

근데 정답이네요? 왜죠? 아이디어는 "두 수의 최대공약수(gcd)를 빠르게 구하고, 최대공약수 이전까지 하나씩 다 해보자" 입니다. 

n=3일때는 틀린것 같은데...그래서 n=3일때 반례가 없을까 고민해 봤는데, 저는 찾지 못헀습니다.

그럼 이걸 푸신 분들은 처음부터 n=3인거는 고려하지 않았던 것인가요? 어떻게 한번에 그렇게 생각하신건지 과정이 궁금합니다.

이 코드에 정말 반례가 없을까요?  정말 얼떨떨합니다...ㅋ;;

shg9411   3년 전

세 수의 최대공약수가 두 수의 최대공약수보다 커질 일은 없기에 문제가 될 것은 없지 않을까요?

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