nusung   1달 전

문제를 저대로 해석해서 DFS를 통해서 풀었습니다.


예제와 제가 만든 몇 개의 간단한 test case에 대해서는 통과하는데


체출하니까 시간초과가 발생합니다.


어디서 어떤 부분에 시간을 줄일 수 있을까요?


혹시 DFS로는 시간관계상 풀지 못하는 건가요?

zlzmsrhak   1달 전

dfs는 모든 경우를 다 탐색하기 때문에 T개의 빈공간에 W개의 움직임을 배치하는 경우의 수

TCW 정도의 시간이 소요되고, 2초를 아득히 넘어가게 됩니다.

그래서 다른 접근 방법이 필요하고, 이 문제의 경우 DP를 사용하면 해결할 수 있습니다.

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