Boj 23250 c++ 하노이 탑 K

정말 공부에 도움이 많이 된 문제. 

하노이의 탑을 옮기는 구조가 3개로 나누어져있다는 것을 이해하는 것이 중요한 문제.

1. n-1개 시작점에서 보조기둥으로 옮기기

2. 마지막 디스크 도착지점으로 옮기기

3. 보조기둥의 n-1개 도착 지점으로 옮기기

4. 1, 2, 3 반복

 

하지만 1번과 3번 또한 각각의 1, 2, 3번으로 이루어져 있다. 때문에 이를 이용하여 이분탐색을 할 수 있다.

찾으려는 지점을 보정해가며 구하는 방식도 존재하지만 필자는 탐색 범위를 줄여나가는 이분탐색으로 풀이하였다.

#include<iostream>
typedef long long int ll;
using namespace std;

ll k;
int n;
void hanoi(int x, int start, int goal, int sub, ll head, ll tail){

   ll mid=(head+tail)/2;
   if(k<mid){
    hanoi(x-1, start, sub, goal, head, mid-1);
   }
   else if(k==mid){
    cout<<start<<" "<<goal;
    return;
   }
   else{
    hanoi(x-1, sub, goal, start, mid+1, tail);
   }

}

int main(){

  cin>>n>>k;
  ll tail=(1LL<<n)-1;
  hanoi(n, 1, 3, 2, 1, tail);

}