[PRGRMS]12946번: 하노이의 탑

문제: https://programmers.co.kr/learn/courses/30/lessons/12946

---

분할정복 문제입니다.

 

N번째 원판을 1->3번으로 이동시키기 위해서는 아래와 같은 과정을 거칩니다. 

 

1. 1~N-1번째까지의 원판을 1->2번으로 이동

2. N번째 원판을 1->3번으로 이동

3. 1~N-1번째까지의 원판을 2->3번으로 이동

 

그러면 다시 N-1번째 원판을 1->2번으로 이동시키기 위해서는 아래와 같은 과정을 거칩니다. 

1. 1~N-2번째 원판을 1->3번으로 이동

2. N-1번재 원판을 1->2번으로 이동

3. 1~N-2번째 원판을 3->2번으로 이동

 

즉, 위 과정을 기저사례까지 반복하기 때문에 아래 두 가지 케이스를 나눠서 재귀로 풀면됩니다.

1. N번째에 할 일

2. 1~N-1번째까지 할 일

---

코드: https://github.com/cotchan/algorithm/blob/main/PRGRMS/%ED%95%98%EB%85%B8%EC%9D%B4%EC%9D%98%20%ED%83%91.java