https://www.acmicpc.net/problem/11729
11729번: 하노이 탑 이동 순서
세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다. 아래 그림은 원판이 5
www.acmicpc.net
중학교 수학 문제에 등장했던 하노이의 탑이다.
재귀를 이용한다. 5개의 링을 옮기는 과정 속에는 4개의 링을 옮기는 과정이 포함된다.
4개의 링을 옮기는 과정 속에는 3개의 링을 옮기는 과정이 포함된다.
이런식으로 끄적이며 생각해보면 재귀라는 아이디어를 얻을 수 있을 것이다.
예를 들어서, 첫번째 자리에 있던 모든 링들을 세번째 자리로 옮긴다고 하자.
이를 위해서는 가장 아래에 깔려있는 가장 큰 링을 빼내야 한다. 이를 위해서는 그것 위에 있는 n - 1 개의 링을 모두 임시적으로 다른 곳에 옮길 필요가 있다.
주의할 것은, 2의 20승을 계산할 때, pow함수의 출력이 의도한대로 나오지 않는다는 것이다. 이를 위해서 1 << n 연산을 이용한다.
#include<iostream>
#include<math.h>
using namespace std;
void hanoi(int src, int dst, int n) {
if (n == 1) {
cout << src << ' ' << dst << '\n';
return;
}
int temp = 6 - src - dst;
hanoi(src, temp, n - 1); //1 ~ n-1 링을 중간지점에 옮긴다
cout << src << ' ' << dst << '\n'; //가장 커다란 링을 목적지로 옮긴다.
hanoi(temp, dst, n - 1); //중간지점에 있던 n - 1 개의 링들을 목적지로 옮긴다.
}
int main(void) {
int n;
cin >> n; //옮기는 링의 개수
//cout << pow(2, n) - 1 << '\n';// 이렇게 쓰면 틀림 n = 20일때 output이 이상해짐
cout << (1 << n) - 1 << '\n'; // 2의 n승 -1
hanoi(1, 3, n);
return 0;
}
재귀로 풀이를 진행할 때는
1. base condition을 명확히 정의한다.
2. 재귀 식을 찾는다.
n개를 옮기려면, n - 1을 다른곳으로 옮긴 이후에 하나 옮기고 다시 n - 1을 목적지로 옮겨야해.. 와 같은
이 때, 이전 과정이 올바르게 작동할 것이라는 가정을 하고, 현재의 함수가 올바르게 결과를 내놓을지 판단한다.
'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글
| 백준 2441번: 별 찍기 - 4 (C++) (0) | 2019.07.14 |
|---|---|
| 백준 2440번: 별 찍기 - 3 (C++) (0) | 2019.07.14 |
| 백준 2439번: 별 찍기 - 2 (C++) (0) | 2019.07.14 |
| 백준 1074번: Z (C++) (0) | 2019.07.14 |
| 백준 1629번 곱셈 (C++) (0) | 2019.07.11 |