[BOJ] 1914. 하노이 탑 - JAVA

🔗 문제

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

1914번: 하노이 탑

 

💻 풀이 및 코드

문제 유형 : 재귀, 임의 정밀도 / 큰 수 연산

 

풀이

N>20 일 때 옮긴 횟수를 출력할 때 주의해야 한다.

N 의 최댓값은 100 이므로, 2^100 - 1 = 1267650600228229401496703205375 은 long 범위도 초과한다.

따라서 자바의 BigInteger 를 사용한다.

BigInteger 의 pow 라는 지수 메소드를 사용해 2^N 을 구하고, substract 메소드로 1 감소시켜준다.

 

( 왜 2^n -1 의 식이 나오는지 설명 → https://e-una.tistory.com/26)

 

느낀 점

• N > 20 일 때는 횟수만 출력하라는 조건을 못봐서 계속 출력 초과와 메모리 초과 에러가 났다. 지문 꼼꼼히 읽자.
• BigInteger  사용

 

전체 코드

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main_bj_1913_하노이탑 {

	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("res/input_bj_1913.txt"));
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();

		BigInteger ans = new BigInteger("2");
		System.out.println(ans.pow(N).subtract(new BigInteger("1")));
		if (N <= 20) {
			hanoi(1, 3, 2, N);
			System.out.println(sb.toString());
		}
		sc.close();
	}

	static void hanoi(int from, int to, int mid, int cnt) { // 1, 2, 3
		if (cnt == 0) {
			return;
		}

		hanoi(from, mid, to, cnt - 1);
		sb.append(from).append(" ").append(to).append("\n");
		hanoi(mid, to, from, cnt - 1);
	}

}

---

Reference

https://emoney96.tistory.com/103

boj 1914 하노이 탑