BOJ 9941 - One Move from Towers of Hanoi

BOJ 9941 - One Move from Towers of Hanoi

BOJ 23250 - 하노이 탑 K

동일한 두 문제이다.

하노이 탑은

$$ dp[n]=2dp[n-1]+1 $$

의 공식이 성립하고 이를 역추적하듯이 코드를 짜면 $K$ 번째 이동이 몇 번째 판이고 어디서 어디로 이동하는지를 $O(N)$에 찾아줄 수 있다.

void solve() {  
   int c = 0;  
   while (1) {  
      int n, k;  
      cin >> k >> n;  
      if (n == 0)break;  
      vi dp(n + 1);  
      for (int i = 1; i <= n; i++) dp[i] = dp[i - 1] * 2 + 1;  
      string s = "AABC";  
      function<void(int, int, int, int)> track = [&](int i, int k, int from, int to) -> void {  
         if (k == dp[i - 1]) {  
            c++;  
            cout << "Case " << c << ":" << ' ' << i << ' ' << s[from] << ' ' << s[to] << endl;  
            return;  
         }  
         int other = 6 - from - to;  
         if (k <= dp[i - 1]) track(i - 1, k, from, other);  
         else track(i - 1, k - dp[i - 1] - 1, other, to);  
      };  
      track(n, k - 1, 1, 3);  
   }  
}