11729_하노이 탑 이동 순서 (JAVA)

11729번: 하노이 탑 이동 순서

 

[문제 풀이 해결 방법]

** 원판 2개인 경우 == hanoi(2, A, B, C)

 

** 원판 3개인 경우 == hanoi(3, A, B, C)

hanoi(3, A, B, C)에는 hanoi(2, A, B, C)가 두 번 포함되어 있다. 이를 그림으로 다시 나타내면

 

 

import java.util.Scanner;

public class Main {
	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);
	}

	public static void hanoi(int N, int start, int via, int end){
		if(N == 1)
			System.out.println(start+" "+end);
		else{
			hanoi(N-1, start, end, via);
			System.out.println(start+" "+end);
			hanoi(N-1, via, start, end);
		}
	}
}

 이렇게 하면 시간초과가 뜬다. 해결방법은 아래처럼 출력을 StringBuilder로 하는것!

import java.util.Scanner;

public class Main {
	public static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();

		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 via, int end){
		if(N == 1)
			sb.append(start+" "+end).append('\n');
		else{
			hanoi(N-1, start, end, via);
			sb.append(start+" "+end).append('\n');
			hanoi(N-1, via, start, end);
		}
	}
}