ekqls4328   7달 전

시간 초과가 뜨는 이유가 뭐에요??

alphago92   7달 전

j를 1부터 시작해서 최소공배수가 될때까지 1씩더해주는 알고리즘을 사용하셨는데요,


시간제한은 1초

테스트케이스가 최대 1000개

입력값의 범위가 최대 45000 으로 나와있습니다


가장 최악의 경우를 생각해볼까요.


그냥 대충 생각해서 43000과 44000의 최소공배수만 보더라도

1892000 이 나옵니다.

즉 for루프를 189만번 돈다는 것이죠


43001과 44000의 최소공배수를 보면

1892044000 이 나옵니다

for루프를 18억번 도는군요;;


대충 편의상 18억번이 최악의 경우라고 생각해봅시다


테스트케이스가 최대 1000개 이므로

for루프를 약 1조 8000억번 돌게됩니다

이쯤되면 왜 시간초과가 나는지 아시겠지요..?


런타임은 컴퓨터 환경에 따라 차이가 있지만

보통 5천만 루틴을 1초로 잡습니다

위의 경우 36000초(10시간)가 걸리게 되네요;;;;


유클리드 호제법이라는 좋은 알고리즘이 있습니다

정말 간단한 알고리즘이니만큼

위키피디아에 검색하셔서 알아두시면 두고두고 도움이 될겁니다


ekqls4328   7달 전

감사합니다 ㅎㅎ

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