onlyhim   5년 전

dp[y][x][k] = 현재 원숭이의 위치가 y,x이고 말 점프횟수가 k일때 최소값

으로 설정하고 다이나믹프로그램이 방법으로 풀었습니다.

대부분의 분들이 큐를 이용한 BFS로 해결했던데, 이 방법이 왜 틀렸는지 이해가 안되서 질문 올립니다.(질문 게시판의 있는 예제는 전부 잘 동작합니다)

감사합니다.

rdd6584   5년 전

위 코드로는 dp테이블에 원하시는 최소값이 들어가지 않습니다. Yxk를 처음 방문할 때의 값이 항상 최소인가?를 생각하시면 될 듯 합니다. 


또한 원하시는 값을 넣으려면 지수시간 복잡도를 피하기 어려워보입니다.

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