nokdoohoboo   9달 전

저는 너무 오랫동안 이 문제가 파이썬으로 시간초과로 인해 안 풀렸어서

해결 방법 공유드립니다.

저는 BFS 사용하여 풀었는데 모든 테스트 케이스가 정답이었음에도 불구하고 시간초과가 떴습니다.

해결방법은 가지치기를 이용했습니다.

"(남은_사다리수 * 2) < (사다리 틀린 개수)" 인 경우,

남은 사다리들을 쓰더라도 해결이 어차피 불가하다는 사실을 이용하여

BFS에서 queue에 넣는 경우의 수를 가지치기하여 입력하니 시간초과가 해결되었습니다.


기존 가지치기 안 한 코드를 C로 그대로 변환 시, 엄청 빠른 속도로 문제 해결 뜨는 것 보고

C, C++도 공부하고 나서 백준에 돌아오기로 했습니다...

zenith82114   9달 전

백트래킹으로 풀면 PyPy3으로는 맞힐 수 있습니다.

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