JArchive 프로그래밍 일기

문제

하노이 탑 이동 순서 백준 11729

"맞았습니다" 코드

#include <bits/stdc++.h>
using namespace std;

int N; // 원반의 개수

void func(int a, int b, int n){
  if(n == 1) {
    cout << a << ' '<< b << '\n'; // a에서 b로 옮긴다.
    return;
  }
  func(a, 6-a-b, n-1);
  cout << a << ' '<< b << '\n'; // a에서 b로 옮긴다.
  func(6-a-b, b, n-1);
}

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> N;
  cout << (1<<N)-1 << '\n'; // 이동 횟수
  func(1, 3, N);
  return 0;
}

리뷰

재귀를 이용한 하노이탑 이동순서 문제다.
혼자 식 세우기 어려웠다.

기둥 번호가 1,2,3번이 있는데. 번호의 합이 6이다.
그래서 n-1개의 원판을 1번에서 2번으로 옮기고.
n번째 원반을 1번에서 3번으로 옮기는데.
이 때 기둥의 번호를 6에서의 뺄셈을 이용해 표현하는 것이 신기했다.

재귀 공부를 하면서 다시 풀어봐야 할 문제다.