테크 로그포스 Tech Log Force
[BOJ][C++] 백준 11729 하노이의 탑 이동순서 본문
하노이의 탑은 설계가 딱!! 들어맞아서 알고나면 참 재밌지만
항상 뚝딱 풀어지지는 않는다...ㅠ
https://shoark7.github.io/programming/algorithm/tower-of-hanoi
이 분 글을 참고해서 풀었다.
탑1, 탑2, 탑3이 있을 때
- 가장 큰 원판(N)을 제외한 나머지(N-1)을 탑1에서 탑2로 옮긴다. // 이 때 탑3을 활용한다.(거쳐서 옮긴다)
- 가장 큰 원판(N)을 탑3으로 옮긴다.
- 나머지(N-1)원판들을 탑3에 다시 옮긴다. // 이 때 탑 1을 활용한다.
요 과정을 반복한다.
n==1이 되면(제일 작은 원판의 이동 차례) 그냥 옮겨준다.
#include <iostream>
#include <cmath>
using namespace std;
void Hanoi(int n, int from, int to, int via) {
if (n == 1) {
cout << from << " " << to << "\n";
}
else {
Hanoi(n - 1, from, via, to);
cout << from << " " << to << "\n";
Hanoi(n - 1, via, to, from);
}
}
int main()
{
int N;
cin >> N;
cout << (int)pow(2, N) - 1 << "\n";
Hanoi(N, 1, 3, 2);
}
'CS > Algorithm & Data Structure' 카테고리의 다른 글
[BOJ][C++] 백준 2798 블랙잭 (0) | 2022.11.22 |
---|---|
[BOJ][C++] 백준 2447 별찍기 -10 (0) | 2022.11.22 |
[BOJ][C++] 백준 10870 피보나치 수 5 (0) | 2022.11.22 |
[BOJ][C++] 백준 10872 팩토리얼 (0) | 2022.11.22 |
[BOJ][C++] 백준 1181 단어 정렬 (0) | 2022.11.22 |
Comments