링크
https://www.acmicpc.net/problem/11729
문제
세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.
한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.
이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.
아래 그림은 원판이 5개인 경우의 예시이다.
입력
첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.
출력
첫째 줄에 옮긴 횟수 K를 출력한다.
두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.
풀이
#include <iostream>
using namespace std;
int k;
void func(int a, int b, int n) {
if (n == 1) {
cout << a << ' ' << b << '\n';
return;
}
func(a, 6 - a - b , n - 1);
cout << a << ' ' << b << '\n';
func(6 - a - b, b, n - 1);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> k;
cout << (1 << k) - 1 << '\n';
func(1, 3, k);
}설명
재귀
n번 원판에만 집중을 해보면 뭐가 어찌됐든 원판을 전부 기둥1에서 기둥3으로 옮길려면 n번 원판을 기둥3으로 옮겨야한다.
1번부터 n-1번 원판들은 전부 비켜줘야하고 더아가 이들은 전부 기둥2로 가야된다. 왜냐하면 저것들중 하나라도 기둥3으로 간다면 작은 원판위에 큰 원판을 둘 수 없다는 규칙 때문에 n번 원판을 기둥3으로 옮길 수 없기 때문이다.
- n-1개의 원판을 기둥1에서 기둥2로 옮긴다.
- 그 후 n번 원판을 기둥3으로 옮긴다.
- 그 다음에 n-1개의 원판을 기둥2에서 기둥3으로 옮긴다.
n-1개의 원판을 원하는 곳으로 옮길 수만 있다면 n개의 원판도 옮길 수 있다. -> 재귀
원판이 1개일 때 원판을 내가 원하는 곳으로 옮길 수 있다.
원판이 k개일 때 옮길 수 있으면 원판이 k+1개일 때에도 옮길 수 있다.
1. 함수의 정의
void func(int a, int b , int n) : 원판 n개를 a번 기둥에서 b번 기둥으로 옮기는 방법을 출력하는 함수
2. base condition
n=1일때 cout << a << ' ' << b << '\n;
3. 재귀식
n-1개의 원판을 기둥 a에서 기둥6-a-b로 옮긴다. : func(a, 6-a-b, n-1); -> 횟수 A번
n번 원판을 기둥a에서 기둥b로 옮긴다. : cout << a << ' ' << b << '\n; -> 횟수 A + 1번
n-1개의 원판을 기둥 6-a-b에서 기둥 b로 옮긴다.: func(6-a-b, b, n-1); -> 횟수 2A + 1번 -> 초항이 1이기 때문에 이 수열의 일반항은 2^k-1이 된다.
🧷 (1<<k) : '<<'은 left shift라고 불리는 비트연산자인데 1을 비트기준으로 k칸 밀으라는 얘기기 때문에 2^k가 된다.
source : 바킹독 실전알고리즘 0x0B강
