https://www.acmicpc.net/problem/11729
재귀 호출에서 가장 기초가 되는 문제이다.
탑이 세 개가 존재하는데 첫번째 탑에 n개의 판이 작은 원판에서 큰 원판까지 꼭대기부터 바닥에 존재한다.
원판 n개를 최소 몇 번의 이동을 하여 첫번째 탑에서 마지막 탑으로 갈 수 있는지 묻는다.
원판의 최소 이동 횟수는 2^n - 1이다.
가장 기초가 되는 문제이니 꼭 집고 넘어가자.
#include <iostream>
#include <cmath>
using namespace std;
void move(int no, int x, int y) { //x에서 y기둥으로 접시 no개를 옮긴다.
if (no > 1) { //첫째 기둥에서 중간 기둥으로 옮긴다.
move(no - 1, x, 6 - x - y);
}
cout << x << ' ' << y << '\n'; //x번에서 y번으로 이동했다는 것을 표시
if (no > 1) {//중간 기둥에서 마지막 기둥으로 옮긴다.
move(no - 1,6 - x - y, y);
}
}
int main() {
int no; //원판의 갯수
long long int cnt; //이동횟수를 셀 변수
cin >> no;
cnt = pow(2, no) - 1; //최소 이동횟수는 2^n - 1, cmath의 pow함수 이용
cout << cnt << '\n';
move(no, 1, 3);
}
'백준' 카테고리의 다른 글
백준2870 - 수학숙제 (0) | 2019.06.19 |
---|---|
백준17213 - 과일서리 (0) | 2019.06.19 |
백준1541 - 잃어버린 괄호 (0) | 2019.06.11 |
백준2012 - 등수 매기기 (0) | 2019.06.11 |
백준1389 - 케빈 베이컨의 6단계 법칙 (1) | 2019.06.11 |