porque0525   3년 전

구글링도 해보고 질문게시판도 봤는데 대체 어디가 시간초과 나는 요소인지 모르겠어요. 

9%에서 자꾸 시간초과가 납니다.ㅜㅜ


가로선을 0개부터 놓는다고 생각하고 DFS를 호출한 다음, 전부 i=i인 경우가 나오면 바로 exit(0)하게 했고

사다리 타기를 실제로 해보는 함수(i_is_i)에서도 i=i가 아닌 경우는 더이상 사다리타지말고 바로 빠져나오게 했거든요.

주로 시간초과가 발생하는 부분이 위 부분들인거 같던데 저는 그렇게 하지 않았는데도 시간초과가 납니다. Pypy3도 시간초과가 납니다

어디서 시간초과가 났을까요...도와주세요ㅜㅜ

porque0525   3년 전

자답합니다.

DFS 에서 사다리들을 뽑을 때 이중 for문으로 뽑아서 헷갈렸는데,

사다리를 놓는건 조합이라 DFS에 인덱스를 같이 호출해야 했습니다.

18번째줄에 index를 같이 호출하고, 밑에 사다리를 뽑는 for문에서 index부터 탐색하도록 해야합니다...저건 순열입니다. 

DFS를 재귀호출할 때마다 0부터 계속 탐색해서 시간초과가 났었나 봅니다.

eo956578   3년 전

감사합니다! 이게 원인이었네요 ㅜㅜ

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