백준 11729번 하노이 탑 이동 순서 자바 Java

백준 10단계 6번 문제 - 11729 하노이 탑 이동 순서

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

11729번: 하노이 탑 이동 순서

 

 

 

---

10. 재귀 (6) 백준 11729번 문제 하노이 탑 이동 순서

---

문제

---

 

 

 

 

 

---

과정 생각해보기

---

 

나는 처음 접했는데, 하노이의 탑은 퍼즐의 일종으로 재귀에선 유명한 예제 중 하나라고 한다

그 횟수를 구하는 공식은 2^n - 1이라고 한다

 

우선 이는 재귀 문제라는 것을 기억하며 원판 n개를 움직이는 횟수를 구하는 함수를 hanoi(n)으로 칭한다

가장 밑에 있는 원판을 장대 3에 옮기기 위해, n-1개의 원판을 장대 2에 옮겨야 한다

이때 hanoi(n-1)만큼 움직인다

 

그럼 이렇게 될 것이다

이후 가장 밑에 있는 원판을 장대 3에 옮기는 횟수는 1번 이므로 1을 더해준다

 

*지금까지 움직인 횟수: hanoi(n-1) + 1

 

이제 다시 장대2에 있는 함수들을 장대3에 옮겨야 하므로

 

다시 한 번 hanoi(n-1)번 움직인다

 

따라서 원판 n개를 움직인 총 횟수는

hanoi(n-1) + 1 + hanoi(n-1)즉, hanoi(n) = 2*hanoi(n-1)+1이 된다

 

따라서 예제에서 n=3일 때 7임을 알고 있으므로

7 = 2 * hanoi(2) + 1

hanoi(2) = 3

 

hanoi(4) = 2 * 7 + 1 = 15

…

즉, n이 차례대로 1, 2, 3, 4, …일 때 1, 3, 7, 15, … 임을 알 수 있고

이는 2^n - 1 임을 알 수 있다

 

원판이 n개일 때 총 2^n - 1번 움직이는 것이다

 

 

---

정답 인정 코드

---

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws IOException{
        BufferedReader  br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        
        sb.append((int)Math.pow(2, n)-1).append("\n");    //횟수 2^n - 1 / 형변환 안 하면 실수형 .0으로 표시
        
        hanoi(n, 1, 2, 3);
        System.out.println(sb);
 
    }
    
    public static void hanoi(int n, int start, int mid, int end) {
        if(n==1) {
            sb.append(start + " " + end + "\n");
        }else {
            hanoi(n-1, start, end, mid);    //1. n-1개를 장대2로 보낸다
            sb.append(start + " " + end + "\n"); //2. 가장 큰 원판을 장대3으로 보낸다 (1회)
            hanoi(n-1, mid, start, end);    //3. 장대2에 있는 n-1개를 장대3으로 보낸다
        }
    }
 
}
 

 

 

 

---

직후 백지 복습

---

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
 
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.valueOf(br.readLine());
        
        sb.append((int)Math.pow(2, n)-1).append("\n");
        
        hanoi(n, 1, 2, 3);
        System.out.println(sb);
    }
    
    public static void hanoi(int n, int start, int mid, int end) {
        if(n == 1) {
            sb.append(start + " " + end + "\n");
        }else {
            hanoi(n-1, start, end, mid);
            sb.append(start + " " + end + "\n");
            hanoi(n-1, mid, start, end);
        }
    }
 
}

 

 

 

---

10단계 재귀 끝!

재귀는 이게 맞나.. 하면서 풀게 된다