[백준] 1914번 하노이 탑 JAVA (자바) 풀이

문제 1914번 

 :  3개의 장대 중 첫번째 장대에 반경이 서로 다른 n개의 원판이 크기 순서대로 쌓여있다

 :  첫번째 장대를 세번째 장대로 옮긴다

    한 번에 한 개의 원판씩 옮기기 가능
    쌓아놓은 원판은 항상 크기별로 (아래로 갈수록 더 크다)

 

 :  이동횟수는 최소

 

 

[입력]

 :  첫 줄에 첫번째 장대에 쌓인 원판 개수 N (1 ≤ N ≤ 100)

[출력]

 :  첫째줄에 옮긴 횟수 출력

 :  두번째 줄부터 K개의 줄까지 수행과정 출력 (N ≤ 20)

    예) 두 정수 A B 출력 = A번째 탑의 가장 위 원탑을 B번째 탑의 가장 위로 옮긴다

 

 :  N > 20 경우 과정 출력 X

 

 

 [설명 예시]

 

• 원반개수 [n = 1]
   
  A → C  1회     
  
  총 1회
  
  
• 원반개수 [n = 2]
  
  A → B  1회
  A → C  1회  
  B → C  1회
  
  총 3회
  
  
• 원반개수 [n = 3]
  
  A → B 3회 ( B에 쌓이는 원반 개수를 2로 만드려면 [n=2] 위 과정 반복)
  
  • A → B
  • A → C
  • B → C
  A → C  1회
  B → C  3회 ( B에 있는 원반 2개를 C로 옮겨야 하므로 [n=2] 위 과정 반복)
  
  • B → A
  • B → C
  • A → C
   총 7회
  
  

< 하노이 규칙 >

1. 임시 기둥에 가장 큰 원반을 제외하고 모두 옮긴다 ▶ F(n-1)
2. 가장 큰 원반을 마지막 기둥에 옮긴다 ▶ 1
3. 임시 기둥에 쌓여진 원반을 마지막 기둥에 마저 옮긴다 ▶ F(n-1)

 

https://gusdnd852.tistory.com/96

• 원반개수 [n = 2]
  
  F(2) = 3회
• 원반개수 [n = 3]
  
  A → B  3회
  A → C  1회
  B → C  3회 
  
  F(3) = 1 + 2F(2) 
          = 1 + 2·3 
          = 7회
          = 2ⁿ-1
  
  
• 원반개수 [n = 4]
  
  A → B  7회
  A → C  1회
  B → C  7회 
  
  F(4) = 1 + 2F(3) 
          = 1 + 2·7
          = 15회
          = 2ⁿ-1

 

하노이 원판 이동 횟수는  2ⁿ-1 이다
n의 최대값이 100 이므로 원판은 최대 12676506000 × (10^20) 번 이동한다
이는 정수형의 가장 큰 타입인 long의 범위를 훨씬 넘어선다

최대 표현 범위보다 큰 수를 저장하게 되면 오버플로우가 발생해 전혀 다른 값이 저장된다

※ 해결방안 → BigInteger 사용

 

< BigInteger >

 

import java.math.BigInteger; 

BigInteger bi = new BigInteger("2");  //문자열 "2"

메서드	설  명
add	덧셈 (this + val)
subtract	뺄셈 (this - val)
multiply	곱셈 (this * val)
divide	나눗셈 (this / val)
remainder	나머지 (this % val)

 

 < Math.pow >

 

거듭제곱 계산을 위한 메서드

 

public class MathPow {
    public static void main(String[] args)  {
        double result = Math.pow(6, 2); //6의 제곱
    }
}

 

 

 BigInteger bi = new BigInteger("2");

 System.out.println(bi.pow(n)sbtract(new BigInteger("1")));           ▶     2ⁿ-1

 

 

 [코드]

import java.util.*;
import java.io.*;
import java.math.*;
public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        BigInteger bi = new BigInteger("2");
        System.out.println(bi.pow(n).subtract(new BigInteger("1")));
        
        if (n <= 20)
            F(n, 1, 2, 3);
    }
    
    public static void F(int n, int A, int B, int C){
        
        if(n==1){
            System.out.println(A+" "+C);
            return;
        }
        F(n-1, A, C, B);
        System.out.println(A+" "+C);
        F(n-1, B, A, C);
        
        return;
    }
}

 

 

 [해설]
     

 :  int n = Integer.parseInt(br.readLine());  첫째줄 수열 개수 입력
 
 :  BigInteger bi = new BigInteger("2");  BigInteger 에 문자열 "2" 생성
 

 :  System.out.println(bi.pow(n).subtract(new BigInteger("1")));  2ⁿ-1의 값을 출력하라
        
 :  if (n <= 20)  n은 최대 20 까지 출가능
            F(n, 1, 2, 3);  F 메서드 시작
  
    
 :  public static void F(int n, int A, int B, int C){  재귀 시작 /  A는 시작탑, B는 거치는 탑, C는 도착탑
        
        if(n==1){  n이 1인 경우는 바로 출력 가능하다
            System.out.println(A+" "+C);  A에서 C로 바로 옮기기
            return;
        }

        F(n-1, A, C, B);  제일 큰 원반 제외한 나머지 원반(n-1)을 시작탑에서 중간탑으로 모두 이동
                                  이동하면서 비어있는 마지막 탑은 맘대로 활용할 것

        System.out.println(A+" "+C); 중간탑에 모두 옮겼으면 제일 큰 원반을 마지막 탑으로 옮기기

        F(n-1, B, A, C); 중간탑에 모여있는 n-1개의 원반 마지막 탑으로 모두 옮기기
                                 이동하면서 비어있는 첫번째 탑은 맘대로 활용할 것
        return;
    }

 

 

[시간 복잡도]

 

시간복잡도는 O(2ⁿ) 

 

 

StringBuilder를 사용해 출력하는 경우 훨씬더 짧은 시간 내에 풀이가 가능하다

수정 코드

import java.util.*;
import java.io.*;
import java.math.*;
public class Main{
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        BigInteger bi = new BigInteger("2");
        System.out.println(bi.pow(n).subtract(new BigInteger("1")));
        
        if (n <= 20)
            F(n, 1, 2, 3);
            System.out.println(sb);
    }
    
    public static void F(int n, int A, int B, int C){
        
        if(n==1){
            sb.append(A+" "+C).append("\n");
            return;
        }
        F(n-1, A, C, B);
        sb.append(A+" "+C).append("\n");
        F(n-1, B, A, C);
        
        return;
    }
}

  

 

 

이제 풀어보러 갈께요 :)

 

 

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

1914번: 하노이 탑

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *