디스크 을 모두 어떤 목표 기둥 로 옮기는 최단 거리를 생각한다. 현재 번 디스크가 이미 에 있으면, 이 디스크는 움직일 필요가 없고 나머지 디스크들의 목표 기둥도 그대로 이다.
현재 번 디스크가 가 아닌 기둥 에 있으면, 번 디스크를 로 옮기기 전에 더 작은 모든 디스크가 나머지 기둥에 모여 있어야 한다. 그 뒤 번 디스크를 한 번 옮기고, 더 작은 디스크들을 다시 로 옮긴다. 따라서 이 경우 거리에는 가 더해지고, 다음에 고려할 더 작은 디스크들의 목표 기둥은 와 가 아닌 나머지 기둥이 된다.
이 과정을 큰 디스크부터 작은 디스크까지 보면 목표 거리는 길이 인 이진수로 표현된다. 각 자리에서 현재 디스크가 현재 목표 기둥에 있으면 그 자리는 , 아니면 이다. 같은 목표 거리를 갖는 상태들은 이 이진수 자리가 모두 같다.
어떤 자리가 이면 그 디스크의 위치는 현재 목표 기둥으로 하나만 정해진다. 어떤 자리가 이면 그 디스크는 현재 목표 기둥이 아닌 두 기둥 중 하나에 있을 수 있고, 선택한 위치에 따라 다음 목표 기둥이 정해진다. 그러므로 목표 거리의 이진수에서 인 자리의 개수를 이라 하면 같은 목표 거리를 갖는 상태는 총 개이고, 입력 상태를 제외하면 개이다.
따라서 이면 No를 출력한다. 그렇지 않으면 개의 선택을 이진 코드로 보아 서로 다른 코드를 개 고르고, 입력 상태에 해당하는 코드만 건너뛰면 된다. 각 코드를 큰 디스크부터 다시 해석하면 조건을 만족하는 상태가 만들어진다.
출력 크기가 이므로 전체 시간 복잡도는 이고, 메모리 복잡도는 이다.
Solution written by GPT5.5
