https://www.acmicpc.net/problem/11729
재귀를 사용해서 풀었습니다.
개인적으로 높은 난이도의 문제인 것 같습니다.
hanoi(a,b,num)
에서 a를 현재 위치, b를 목표 위치로 두고, num을 현재 보고 있는 원판으로 잡았습니다.
c는 나머지 한 탑의 위치입니다.
#include<iostream>
using namespace std;
int n;
void hanoi(int a, int b, int num) {
int c = 6 - a - b;
if (num == 1) {
cout << a << ' ' << b << '\n';
//이해하기 힘드신 분은 아래처럼 num도 출력해보세요.
//cout << a << ' ' << b << ' ' << num << '\n';
return;
}
else {
hanoi(a, c, num - 1);
cout << a << ' ' << b <<'\n';
//cout << a << ' ' << b << ' ' << num << '\n';
hanoi(c, b, num - 1);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
cout << (1 << n) - 1 << '\n';
hanoi(1,3,n);
}
- 혼잣말
굉장히 어려웠던 문제였다. 문제를 푸는 건 둘쩨치고 접근하기도 힘들었다.
생각하다가 바로 다른 사람의 코드를 봤지만…
다른 사람의 코드를 봐도 이해하는데 한참 걸렸다.
재귀를 이해하는데 도움(?)이 된 것 같다.