[백준 / BOJ] 11729번 하노이 탑 이동 순서 (C++, Python)

링크 : https://www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

---

문제

---

문제 풀이

재귀로 풀지 않으면 접근 방식이 참 어려울 것 같은 문제다.

 

찬찬히 생각해보면, 이동 과정을 통째로

 

i) n-1개의 원판을 2번째 장대로 옮긴다.

ii) 제일 밑에 있는 원판을 3번째 장대로 옮긴다.

iii) 2번째 장대에 있는 원판들을 3번째 장대로 옮긴다.

 

라고 요약할 수 있다. ii)번째 과정을 생각해보자. 이는

 

1) 2번째 장대의 맨 마지막 원판을 제외한 원판들을 1번째 장대에 옮긴다.

2) 2번째 장대의 맨 마지막 원판을 3번째 장대에 옮긴다.

3) 1번째 장대에 있던 원판들을 3번째 장대에 옮긴다.

 

인데, 이는 재귀적으로 구현할 수 있다. 결국 일련의 과정이 막대의 위치만 달라졌을 뿐 원래의 문제의 축소된 형태이기 때문이다.

 

 

C++ 코드 전문

 

Python 코드 전문

 

소감