[백준] 23250 : 하노이K

https://www.acmicpc.net/problem/23250

문제 분석

일단 하노이 탑의 방식부터 다시 정리하자. 알다시피 하노이 탑은 재귀적으로 표현가능하다. N 크기의 탑을 옮기는 과정은 N-1 크기의 탑을 옮기는 과정으로 표현가능하다. N-1의 탑을 잠시 다른데 옮기고 N의 블록을 옮기고 다시 N-1의 탑을 옮기면된다. 이 방법만이 최소면서 유일한 하노이탑 이동 방식이다. 

 

N 크기의 탑을 i위치에서 k위치로 옮기는 경우 1. N-1크기의 탑을 i에서 j로 옮긴다. 2. N을 i에서 k로 옮긴다. 3. N-1 크기의 탑을 j에서 k로 옮긴다. N=1 일시는 바로 i에서 k로 옮긴다.

 N의 크기의 탑을 이동하는 최소 비용은 $2^N-1$만큼의 이동을 필요로 한다.$($하단에 유도과정이 있다.$)$ 이때, N의 크가가 최대 60이므로 최대 $2^{60}-1 \approx 10^{18}$의 이동을 필요로 한다. 그럼, 하노이탑의 순서를 순서대로 첫번째 부터 K번째 까지 가는 것은 시간복잡도상 불가능하다. 이를 위해서 앞서 구한 세가지 케이스로 나누어 순서를 구하면된다.

 

$DP[N]$ : N 크기의 하노이 탑을 이동시키는데 드는 이동 횟수
$DP[N] = 2DP[N-1]+1$,  $DP[1]=1$
$DP[N]=2^N-1$

 N의 탑을 이동시키는것은 앞서서 3가지 과정으로 분리가 가능했다. 그리고 $DP[N]=2^N-1$임을 위에서 구한 상태이다. 그렇다면 DP[N-1]+1을 기준으로 K값에 따라 3가지 케이스에 따른 순서를 재귀적으로 호출하면 된다. 이때 위와마찬가지로 N=1, K=1인 케이스는 별도로 체크하면된다.

$S(N, K, i, j)$ : N크기의 탑을 i에서 j로 이동시 K번째 순서의 이동
$($i,j,k는 i가 1이고 k가 2이면 j가 3이 되는 식으로 1,2,3 중에서 두 개가 정해지면 남은 하나는 나머지로 자동 할당$)$

$(K<DP[N-1]+1)$ : $S(N-1,K,i,j)$                     
$(K=DP[N-1]+1)$ : i에서 k로 이동                                 
$(K>DP[N-1]+1)$ : $S(N-1,K-(DP[N]+1)),j,k)$  
N=1, K=1일 시 i에서 k로 이동

문제 해결 전략

 위의 내용을 그대로 구현하면된다. 재귀 호출이 아니라 반복문으로도 구현가능하지만 실제 성능차이가 거의 없으며 가독성이 재귀에 비해 떨어져 코드는 재귀를 사용한 버전으로 올렸다. 

코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

//문제분석
//하노이탑 문제는 i위치에서 k위치로 n크기의 탑을 옮기려면  ()
//1. i위치에서 j위치로 n-1 크기의 탑을 옮기고
//2. i위치에서 k위치로 블록 옮기고
//3. j위치의 k위치로 n-1크기의 탑을 옮기기   
//다음 3가지 순서로 이루어진다.
//이떄 올기는데 드는 횟수를 DP[N]으로 보면
//DP[N]=1+2DP[N-1], DP[1]=1 으로 
//이를 일반식으로 표현하면 DP[N]=2^N-1 으로 표현가능하다.
//이떄, 최대 N에대해서 DP[60]=2^60-1=1000^6-1 이므로 직접 모든 순서를 시행하는 건 불가능하다.
//N개의 탑을 i에서 k로 옮길떄 K번쨰 이동을 S(N,K,i,k)라 하면
//S(N,K,i,k)는 다음 3가지 경우 가 나올 수 있다.
//1. S(N-1,K,i,j)             (K<=DP[N-1])
//2. (i,k)                    (K=DP[N-1]+1)
//3. S(N-1,K-(DP[N]+1)),j,k)  (K>DP[N-1]+1)
//그리고 재귀의 기본으로 N=1, K=1일때 (i,k)를 출력한다.

//=====================================================================
//해결전략
//제곱식과 재귀 함수 구현
//끽해봤자 60번 호출이라 그냥 재귀 사용
//=====================================================================
//필요자료형
//변수
//
//함수
//

using PII = pair<int,int>;

PII GetMoveInK(int N, long long K, int i, int k){
    if (N==1 && K==1) return {i,k};
    long long criterion = (1LL<<(N-1))-1;
    int j=6-(i+k);
    if (K<=criterion) return GetMoveInK(N-1, K, i, j);
    else if (K==(criterion+1)) return {i,k};
    else return GetMoveInK(N-1, K-criterion-1, j, k);
}

int main()
{
    int N;
    long long K;
    cin >> N >> K;

    PII ans=GetMoveInK(N,K,1,3);
    cout << ans.first << " " << ans.second << endl;
}