leaps   2년 전

처음에 DP를 [202][202][2]로 잡고 풀었습니다.

일단 BFS로 접근하기 때문에, 이동하는 위치에 도달 했을 때 항상 이동 횟수가 최소가 됩니다.

다른 점은 그 위치에 도달했을 때, 말로 도달했냐, 아니면 걸어서 도달했냐 차이인데, 이 두개만 dp로 두니까 틀렸다고 나옵니다.

어떠 한 지점을 말처럼 이동했을 때 도달하게 되면 그 지점은 항상 '말'을 이용하여 도달할 수 있는 최소지점이 되고,

다음에 말처럼 이동해서 도달하더라도 어쩌피 말 이동횟수가 이전보다 적거나 같을테니 의미없는것 아닌가요?

반례가 궁금합니다..

-> 질문 DP[y][x][j] 로 두고, j를 0, 1로 두고, 0은 그냥 이동해서 도달했을 때, 1은 말로 이동해서 도달했을 때로 잡고 풀면 왜 안되는지..

leaps   2년 전

네 BFS Queue 안에는 현재 위치에서 K가 몇번 남았는지 기록해놨습니다.

그러나 dp상으로는 고려할 필요가 없지 않나요? 굳이 dp[y][x][31]을 만들어서 처리해야되나요?

현 위치에 말로 도착한 것과, 원숭이로 도착한 것 두가지로만으로도 충분할 거라고 생각했는데 안되네요

djm03178   2년 전

앞으로 말처럼 움직이는 횟수가 몇 회 남았는지에 따라 끝까지 도달하는 게 불가능할 수도, 앞으로 최소 몇 번 움직여야 하는지 다를 수도 있는데 이를 어떻게 저장하셨다는 것인지 모르겠습니다.

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