개발하고싶은 블로그

[문제] 이동 규칙 다음에 이동할 수 있는 거리(광년)는 현재 이동거리의 현재 이동거리, +1 또는 -1이다. 현재 3을 이동했다면 다음에 이동할 수 있는 거리는 2, 3, 4 중에 하나이다. 마지막 이동거리는 1이여야 한다. 위의 이동 규칙을 가지고 현재 x지점에서 y지점으로 가기 위해선 최소 몇 번 움직여야 할까? 처음에는 단순하게 brute-force, BFS를 사용하면 되지 않을까라고 생각했다. 처음에 1을 움직이고 그다음에는 1, 2를 큐에 넣고 그 다음에도 또 1,1,2,3을 큐에 넣고 이런 식으로 전체 탐색을 하다가 현재 지점이 y이면서 이동거리가 1였을 때를 찾으면 되지 않을까라고 생각했다. 하지만… 메모리 초과가 발생했다. 당연하게도 처음에 이동할 때를 제외하고는 3번씩 (-1, 현재, ..