문제 : 하노이 탑
시간 제한 : 6 sec
메모리 제한 : 128 MB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
import java.io.*;
import java.math.BigInteger;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
BigInteger re = BigInteger.ONE;
for (int i = 0; i < n; i++) {
re = re.multiply(BigInteger.TWO);
}
re = re.subtract(BigInteger.ONE);
System.out.println(re);
if(n<=20)
move(n,1,3);
br.close();
bw.flush();
bw.close();
}
public static void move(int n, int i, int j) {
// TODO Auto-generated method stub
if(n==1) {
System.out.println(i+" "+j);
return;
}
if(n>1) {
move(n-1,i,6-i-j);
}
System.out.println(i+" "+j);
if(n>1) {
move(n-1,6-i-j,j);
}
}
}
|
cs |
하노이 탑 문제를 알고리즘 공부하다가 보게 되어서 백준에서 풀어보고 싶었음.
일단 옮기는 횟수는 2^n-1 이라는 걸 알게 되었다.
결국 BigInteger 사용해서 횟수 먼저 출력하고
n이 20 이하일 때 알고리즘 사용해서 옮기는 거 출력했음.
하노이 탑 알고리즘은 어려운데 외워야하는 것도 아닐텐데 이해해야겠지,,,,,
자주 봐서 까먹지 말자
'algorithm > 문제 풀이' 카테고리의 다른 글
백준 10989번 (수 정렬하기 3) Java 11 계수 정렬 (0) | 2021.02.08 |
---|---|
백준 2740번 (행렬 곱셈) 자바 Java11 (0) | 2021.01.26 |
백준 2747번 (피보나치 수) 자바 Java 11 (0) | 2021.01.23 |
백준 1924번 (2007년) 자바 Java11 (0) | 2021.01.22 |
백준 2751번 (수 정렬하기 2) C++ (0) | 2021.01.13 |