이 문제는 이동횟수 뿐만 아니라 이동 과정도 출력해야하기 때문에 다들 재귀로 푸는 것 같습니다.

단순히 이동횟수만 출력하는 문제라면 질문자님께서 말씀하셨듯이 동적계획법으로 중복으로 구해지는 부분을 건너뛸 수 있습니다.

DP를 사용할 수 있는 문제는 Optimal Substructure, 즉 최적 부분 구조 문제에서 사용할 수 있습니다.

하노이탑 문제 같은 경우 전체 문제를 풀기 위해 부분 문제를 반복해서 풀어야 하는 것은 맞지만, 작은 문제의 정답이 전체 문제의 정답이 되는것은 아니라고 생각합니다.

n=1의 경우 답은 1->3입니다. 하지만 n=2를 풀때, 우리는 이 1->3을 그대로 쓸 수 없습니다. 왜냐하면 가장 아래의 원판이 3번 막대로 가야하기 때문입니다.

물론 n=3에선 다시 1->3이 첫번째 과정이 되나, 이미 두번째 원판에 대해서도 이미 구한 1->3을 쓸 수 없습니다. n=3의 첫번쨰 원판처럼 처럼 중복되는 움직임이 존재는 하나, 원판의 개수에 따라 같은 원판에 중복되지 않는 움직임이 계속 생기고, 이에 DP를 쓰기는 어려울 것 같습니다.

추가적인 이유를 더 보자면, 애초에 메모이제이션이 필요하지 않습니다. 대표적인 DP문제인 피보나치 수열의 경우 다음 피보나치 수를 구하는데 반드시 이전 결과값이 필요합니다. 물론 하노이 탑도 진행된 상태에 따라 결과가 달라지겠지만, 여기에는 이전의 이동 과정이 필수적이진 않습니다. 즉, 다음 이동 과정을 출력하는데 있어 이전의 이동 과정을 다시 계산할 필요가 없습니다.

추가로 정답을 맞추신 코드는 지우시는게 좋을 것 같습니다. 질문검색은 아직 풀지 않은 사람들도 모두 볼 수 있는 공간이기에 주의해주세요.

추가로 stackoverflow의 이 글을 보시면 좋을 것 같습니다.

감샤햡니다