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

문제

느낀점

재귀함수를 써서 풀어야 하는 게 쉽지 않았다. 하노이 탑의 알고리즘과 점화식을 잘 몰랐는데, 이 부분은 고민해도 잘 풀리지 않아서 https://st-lab.tistory.com/96 이 분의 블로그를 참고했다. 다시 한 번 더 풀어봐야겠다..!

풀이

package december_first;

import java.util.Scanner;

public class baek_11729 {

	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		
		System.out.println((int)(Math.pow(2, N)-1));
		
		Hanoi(N, 1, 2, 3);
		System.out.println(sb);
		
	}

	static void Hanoi (int N, int start, int mid, int to) {
		
		if (N == 1) {
			sb.append(start + " " + to + "\n");
			return;
		}
		
		Hanoi(N-1, start, to, mid);
		
		sb.append(start + " " + to + "\n");
		
		Hanoi(N-1, mid, start, to);
		
	}
}