[백준/C++] 11729번: 하노이 탑 이동 순서

란지·2021년 9월 24일
0

백준

목록 보기
7/13

문제

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.
이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

아래 그림은 원판이 5개인 경우의 예시이다.

문제보기

입력

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.

출력

첫째 줄에 옮긴 횟수 K를 출력한다.

두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.

예제


아이디어

옮긴 횟수 K는 2의 제곱씩 증가한다.
재귀함수를 이용하여 수행 과정을 출력한다. 시작기둥->중간기둥, 중간기둥->목표기둥을 나누어 구현한다.

코드

#include <iostream>
#include <cmath>
using namespace std;

void move(int N, int s, int e) {
	if (N > 1) {
		move(N - 1, s, 6 - s - e);
	}
	cout << s << " " << e << "\n";
	if (N > 1) {
		move(N - 1, 6 - s - e, e);
	}
}
int main() {
	int N;
	cin >> N;
	int K = 0;
	for (int i = 1; i <= N; i++) {
		K +=  pow(2, i - 1);
	}
	cout << K << "\n";

	move(N, 1, 3);

	return 0;
}

시행착오

Do it 알고리즘 교재 속 코드를 참고하여 작성하였다.
적혀 있는 함수를 보고 이해할 수는 있지만, 아무것도 없는 상태에서 생각할 수 없을 것 같다.
제곱할 때 pow함수는 생각하였으나 cmath 라이브러리를 include 해주지 않아 컴파일 에러가 발생하였다.

profile
콤퓨타공학과

0개의 댓글