windflower   6년 전

반복문에서 종료 조건은 해당 년도를 찾거나, 종말의 날 다음 해인 1.1이 나오면 종료하도록 했습니다.

정수론적으로 무한루프를 돌지는 않을 것 같은데 어디서 시간 초과가 일어나는 걸까요??ㅜㅜ

rdd6584   6년 전

O(MN)으로 대략 반복문을 16억번 정도 돌게 됩니다.

시간복잡도를 최적화 시켜보세요.

jh05013   6년 전

질문 검색을 누르면 반례가 나옵니다.

windflower   6년 전

질문 검색에 나온 반례는 거의 다 해봤는데 결과가 나와서요ㅜㅜ 제가 직접 예시를 만들어서도 해봤는데도 결과가 나왔구요... 지금 시간복잡도를 줄일 수 있는 방법을 생각해 보고 있습니다!!

jh05013   6년 전

"반례"뿐만이 아니라, 왜 안 돌아가는가에 대한 답변도 포함합니다. 일일히 1씩 더하는 코드가 이것뿐일 리는 없죠.

물론 반례도 있습니다.

https://www.acmicpc.net/board/...

rdd6584   6년 전

https://www.acmicpc.net/board/...
JH님이 직접 작성하신 이 예제는 해보셨나요? 대략 2초정도 나오는거 같네요.


이거 말고도 시간초과 관련 질문이 열개정도는 더 있는 것 같네요.

djm03178   6년 전

이 문제는 효율적인 알고리즘을 쓰더라도 T가 커서 20MS 이상은 쉽게 나옵니다. 1씩 더하는 걸로는 상상을 초월하게 오래 걸립니다.

windflower   6년 전

고수님들 감사합니다!! 덕분에 해결 했어요!!

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