์ฌ๊ท ํจ์๋ฅผ ์ด์ฉํ ํ๋ ธ์ด ํ
๋ฌธ์
https://www.acmicpc.net/problem/11729
11729๋ฒ: ํ๋ ธ์ด ํ ์ด๋ ์์
์ธ ๊ฐ์ ์ฅ๋๊ฐ ์๊ณ ์ฒซ ๋ฒ์งธ ์ฅ๋์๋ ๋ฐ๊ฒฝ์ด ์๋ก ๋ค๋ฅธ n๊ฐ์ ์ํ์ด ์์ฌ ์๋ค. ๊ฐ ์ํ์ ๋ฐ๊ฒฝ์ด ํฐ ์์๋๋ก ์์ฌ์๋ค. ์ด์ ์๋์น๋ค์ด ๋ค์ ๊ท์น์ ๋ฐ๋ผ ์ฒซ ๋ฒ์งธ ์ฅ๋์์ ์ธ ๋ฒ์งธ ์ฅ๋๋ก ์ฎ๊ธฐ๋ ค ํ๋ค. ํ ๋ฒ์ ํ ๊ฐ์ ์ํ๋ง์ ๋ค๋ฅธ ํ์ผ๋ก ์ฎ๊ธธ ์ ์๋ค. ์์ ๋์ ์ํ์ ํญ์ ์์ ๊ฒ์ด ์๋์ ๊ฒ๋ณด๋ค ์์์ผ ํ๋ค. ์ด ์์ ์ ์ํํ๋๋ฐ ํ์ํ ์ด๋ ์์๋ฅผ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ๋ผ. ๋จ, ์ด๋ ํ์๋ ์ต์๊ฐ ๋์ด์ผ ํ๋ค. ์๋ ๊ทธ๋ฆผ์ ์ํ์ด 5
www.acmicpc.net
#include <iostream>
using namespace std;
void hanoi(int n, int from, int mid, int to)
{
if (n == 1)
cout << from << ' ' << to << '\n';
else {
hanoi(n - 1, from, to, mid);
cout << from << ' ' << to << '\n';
hanoi(n - 1, mid, from, to);
}
}
int main()
{
int k;
cin >> k;
cout << (1 << k) - 1 << '\n'; // 2^k - 1
hanoi(k, 1, 2, 3);
}