본문 바로가기
Algorithm/Baekjoon

Baekjoon 1914 하노이 탑 JAVA

by Hunveloper 2022. 2. 5.
728x90
 

1914번: 하노이 탑

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로

www.acmicpc.net

문제

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

  1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
  2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

아래 그림은 원판이 5개인 경우의 예시이다.

입력

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 100)이 주어진다.

출력

첫째 줄에 옮긴 횟수 K를 출력한다.

N이 20 이하인 입력에 대해서는 두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다. N이 20보다 큰 경우에는 과정은 출력할 필요가 없다.

풀이

원판의 이동횟수는 2^-1 이다.

문제에서 원판이 20개 이상이면 경로를 출력하지 않고, 이동횟수만 출력하면 되기에 횟수를 구하는 함수와 이동경로를 구하는 함수를 두개 구현하였다.

원판이 100개까지 들어오기에 int, long으로는 2^32, 2^64 밖에 안되서 BigInteger를 이용하여 횟수를 구해준다.

코드
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.math.BigInteger;
import java.util.Scanner;

public class Main {
	static int n;
	static BigInteger cnt = new BigInteger("1");
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static String str = "";

	public static void hanoi(int k, int from, int temp, int to) throws IOException {
		if (k == 0)
			return;
		hanoi(k - 1, from, to, temp);

		str = from + " " + to + "\n";
		bw.write(str);

		hanoi(k - 1, temp, from, to);
	}

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		for(int i=0;i<n;i++)
			cnt=cnt.multiply(new BigInteger("2"));
		cnt=cnt.subtract(new BigInteger("1"));
		System.out.println(cnt);
		if (n <= 20) {
			hanoi(n, 1, 2, 3);
			bw.close();
		}
	}
}
728x90
728x90

'Algorithm > Baekjoon' 카테고리의 다른 글

Baekjoon 1244 스위치 켜고 끄기 JAVA  (0) 2022.02.05
Baekjoon 15964 이상한 기호 JAVA  (0) 2022.02.05
Baekjoon 1913 달팽이 JAVA  (0) 2022.02.05
Baekjoon 10974 모든 순열 JAVA  (0) 2022.02.04
Baekjoon 11653 소인수분해 JAVA  (0) 2022.02.04

댓글