yyyy7089   2년 전

다음은 2747번 문제를 푸는 c++ 소스 코드입니다.

https://www.acmicpc.net/source...

코드를 보면 아시겠지만, 컴파일 시간에 나이브하게 46번째 피보나치 수까지를 재귀로 구함에도, TLE가 나지 않습니다.

발견한 사람에 따르면, 약 2분 이내로 컴파일이 끝날 경우 CE를 받지 않기 때문에, 컴파일 중에 답을 구해도 된다고 합니다.

이와 같은 풀이는 채점 서버에 부하를 일으킬 수 있으므로 조치가 필요하다고 생각됩니다.

r4pidstart   2년 전

컴파일러 자체에 컴파일 타임 프로그래밍 깊이에 제한이 있어요. 생각보다 꽤 작습니다. 피보나치 수백선에서 끊길거예요.

별 걱정은 안 해도 될 것 같슴다.

yyyy7089   2년 전

2분이면 충분히 긴 시간이라고 생각됩니다. 런전처로 풀면 저장해야 하는 값이 너무 많아서 런전처로 못 푼다든지 하는 문제들을 해결할 수 있을 가능성이 있습니다.

r4pidstart   2년 전

아뇨 2분동안 안 돌아요. 한번 짜서 제출해보셔용 컴파일시 연산가능한 횟수가 정해져있어요. 이 이상 넘어가면 컴파일 에러날거예요

https://www.acmicpc.net/source...

이거 제출해보시면 될 듯

yyyy7089   2년 전

그렇군요. 제가 정확히 몰랐네요. 알려주셔서 감사합니다.

jonghyuk1203   2년 전

제가 2분정도 이내라고 말했었던건 2년전 기준이라 달라진 부분이 많이 있을수도 있어요. 

저 코드는 1달전이긴 한데 그때는 시간을 재진 않았거든요.

피보나치 수2 문제에서 실험을 했었을때 2분정도 뒤에 CE가 나왔었기 때문에 했던 말이었습니다.

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