kfc   4년 전

왜 시간초과 뜨는지 알수있을까요??

hs6735   3년 전

저도 비슷하게 짰는데, 똑같이 시간초과가 뜨네요... 왜그런거죠 ㅠㅠ 고수님들 좀 알려주세요 ㅠㅠ 시간복잡도는O(N)인것 같은데...

miles94   2년 전

저도 이  문제로 똑같이 시간초과 나와서 굉장히 고민을 많이 했는데,

10007 에 대한 나머지를 return 할 때 구하는게 아니라 저장할 때 하면 시간초과가 안나더라구요.

다시 말해서,

D[n]=Square(n-1)+(2*Square(n-2)); 

 return D[n]%10007;

이 부분 대신에

D[n] = (Square(n-1) + 2*Square(n-2))%10007;

return D[n];

은 시간초과가 안납니다. 

아마 위의 경우로 해도 정답은 맞을 겁니다. 하지만 D[n] 값은 10007 이상의 값이 들어가게 됩니다.

하지만 아래의 경우로 하면 D[n] 값 저장 자체를 10007 로 나눈 값을 저장하기 때문에 , 이후의 D[n] 계산이

더 빠릅니다. 사실 상식적으로 함수의 return 값 자체가 10007 을 넘지 못하므로 , 작성자님 처럼 코드를 짜도

D[n] 값에 저장되는 값에 더해지는 값은 3* 10007 보다 작긴 하지만, 저장되는 값 자체의 제한을 걸지 않았기 떄문에 꽤 큰 수가 저장될 것입니다.

아마 10007 이라는 뜬금없는 숫자를 준 것이, Testcase 에 대해서 시간초과가 나게끔 threshold 를 잡은 것 같습니다.

추가로 첨부 사진을 보면, 위의 경우가 작성자님 처럼 D[n] 을 저장할 때 %10007 하지 않고, D[n] 을 return 할 때 %10007 을 한 것이고, 아래가 D[n] 저장 자체를 %10007 로 한 것입니다. D[n] 값을 보면, 계산량의 차이가 날 것 이라는 것을 알 수 있습니다.
88df1c57-1772-449c-a856-fe28ce72dd9e

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