jihoon7171   1년 전

만약 모든 칸이 빈칸이라면, 총 81칸의 칸을 백트래킹하면서 확인해야하는데
이러면 시간초과걸리는거 아닌가요 ...?
시간복잡도가 좀 헷갈리네요 ㅜ 

백트래킹이라 생각했지만 모든칸이 빈칸이면 시간이 너무오래걸릴거같아서 백트래킹이 아니라 판단했는데, 문제 분류에는 백트래킹이라되어있어서 틀렸다는걸 알았습니다

제 생각이 왜 틀렸는지 혹시 도움을 주실 분 계신가요 ??

zenith82114   1년 전

모든 칸이 빈칸이면 가능한 답이 매우 많기에 시간이 거의 걸리지 않습니다. 제 코드는 0.002초만에 종료합니다.

반대로 숫자들이 어느 정도 차 있고 답이 몇 가지 안 되는 경우에는, 말씀하신 대로 단순한 백트래킹으로 풀리지 않을 입력들이 있을 수 있습니다. 그러나 그런 입력은 주지 않겠다는 것이 "제한"에 적힌 문장이 뜻하는 바입니다.

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