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 8년 전
시간 초과가 뜨는 이유가 뭐에요??