15684번 - 사다리 조작
저는 너무 오랫동안 이 문제가 파이썬으로 시간초과로 인해 안 풀렸어서
해결 방법 공유드립니다.
저는 BFS 사용하여 풀었는데 모든 테스트 케이스가 정답이었음에도 불구하고 시간초과가 떴습니다.
해결방법은 가지치기를 이용했습니다.
"(남은_사다리수 * 2) < (사다리 틀린 개수)" 인 경우,
남은 사다리들을 쓰더라도 해결이 어차피 불가하다는 사실을 이용하여
BFS에서 queue에 넣는 경우의 수를 가지치기하여 입력하니 시간초과가 해결되었습니다.
기존 가지치기 안 한 코드를 C로 그대로 변환 시, 엄청 빠른 속도로 문제 해결 뜨는 것 보고
C, C++도 공부하고 나서 백준에 돌아오기로 했습니다...
댓글을 작성하려면 로그인해야 합니다.
nokdoohoboo 9달 전
저는 너무 오랫동안 이 문제가 파이썬으로 시간초과로 인해 안 풀렸어서
해결 방법 공유드립니다.
저는 BFS 사용하여 풀었는데 모든 테스트 케이스가 정답이었음에도 불구하고 시간초과가 떴습니다.
해결방법은 가지치기를 이용했습니다.
"(남은_사다리수 * 2) < (사다리 틀린 개수)" 인 경우,
남은 사다리들을 쓰더라도 해결이 어차피 불가하다는 사실을 이용하여
BFS에서 queue에 넣는 경우의 수를 가지치기하여 입력하니 시간초과가 해결되었습니다.
기존 가지치기 안 한 코드를 C로 그대로 변환 시, 엄청 빠른 속도로 문제 해결 뜨는 것 보고
C, C++도 공부하고 나서 백준에 돌아오기로 했습니다...