쉬운 하노이 문제

디스크 $i,i+1,\cdots,N$을 모두 어떤 목표 기둥 $t$로 옮기는 최단 거리를 생각한다. 현재 $i$번 디스크가 이미 $t$에 있으면, 이 디스크는 움직일 필요가 없고 나머지 디스크들의 목표 기둥도 그대로 $t$이다.

현재 $i$번 디스크가 $t$가 아닌 기둥 $a$에 있으면, $i$번 디스크를 $t$로 옮기기 전에 더 작은 모든 디스크가 나머지 기둥에 모여 있어야 한다. 그 뒤 $i$번 디스크를 한 번 옮기고, 더 작은 디스크들을 다시 $t$로 옮긴다. 따라서 이 경우 거리에는 $2^{N-i}$가 더해지고, 다음에 고려할 더 작은 디스크들의 목표 기둥은 $a$와 $t$가 아닌 나머지 기둥이 된다.

이 과정을 큰 디스크부터 작은 디스크까지 보면 목표 거리는 길이 $N$인 이진수로 표현된다. 각 자리에서 현재 디스크가 현재 목표 기둥에 있으면 그 자리는 $0$, 아니면 $1$이다. 같은 목표 거리를 갖는 상태들은 이 이진수 자리가 모두 같다.

어떤 자리가 $0$이면 그 디스크의 위치는 현재 목표 기둥으로 하나만 정해진다. 어떤 자리가 $1$이면 그 디스크는 현재 목표 기둥이 아닌 두 기둥 중 하나에 있을 수 있고, 선택한 위치에 따라 다음 목표 기둥이 정해진다. 그러므로 목표 거리의 이진수에서 $1$인 자리의 개수를 $M$이라 하면 같은 목표 거리를 갖는 상태는 총 $2^M$개이고, 입력 상태를 제외하면 $2^M-1$개이다.

따라서 $2^M-1<K$이면 No를 출력한다. 그렇지 않으면 $M$개의 선택을 이진 코드로 보아 서로 다른 코드를 $K$개 고르고, 입력 상태에 해당하는 코드만 건너뛰면 된다. 각 코드를 큰 디스크부터 다시 해석하면 조건을 만족하는 상태가 만들어진다.

출력 크기가 $O(NK)$이므로 전체 시간 복잡도는 $O(N+NK)$이고, 메모리 복잡도는 $O(N)$이다.

Solution written by GPT5.5