Study hard
(c++)백준 11729번: 하노이 탑 이동 순서 본문
https://www.acmicpc.net/problem/11729
[풀이]
하노이의 탑 알고리즘
아래 순서대로 재귀
1. 맨 아래 원판을 제외하고 나무지 원판 모두를 tmp장대로 옮긴다.
2. 맨 아래 원판을 to장대로 옮긴다.
3. 남은 tmp장대에 있는 판 모두 to장대로 옮긴다.
옮긴 횟수를 출력한 뒤 수행 과정을 출력해야 하므로 vector에 수행과정을 정장해두고 재귀가 끝난 뒤 한꺼번에 출력해주었다.
#include <iostream>
#include <vector>
#include <cstdio>//printf, scanf
using namespace std;
struct Move {
int from, to;
};
int cnt = 0;
vector<Move>v;//수행 과정 저장
void hanoi(int N, int from, int tmp, int to) {
if (N == 1) {
v.push_back({ from,to });
cnt++;
return;
}
hanoi(N - 1, from, to, tmp);
v.push_back({ from,to });
cnt++;
hanoi(N - 1, tmp, from, to);
}
int main() {
int N;
scanf("%d", &N);
hanoi(N, 1, 2, 3);
printf("%d\n",cnt);
for (int i = 0; i < v.size(); i++) {
printf("%d %d\n", v[i].from, v[i].to);
}
return 0;
}
'백준 > 분할 정복' 카테고리의 다른 글
(c++)백준 2448번: 별 찍기 - 11 (0) | 2020.06.30 |
---|---|
(c++)백준 2447번: 별 찍기 - 10 (0) | 2020.06.30 |
(c++)백준 1992번: 쿼드트리 (0) | 2020.06.30 |
(c++)백준 1780번: 종이의 개수 (0) | 2020.06.25 |
(c++)백준 11728번: 배열 합치기 (0) | 2020.06.25 |