백준 11729번 - 하노이 탑(Java 8)

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

11729번: 하노이 탑 이동 순서

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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());
        System.out.println(hanoi(N));
        System.out.println(getHanoiPath(N,1,2,3));
    }
    static int hanoi(int N){
        if(N == 1) return 1;
        if(N == 2) return 3;
        return 2*hanoi(N-1)+1;
    }
    static String getHanoiPath(int N, int num1, int num2, int num3){
        if(N == 1){
            return num1+" "+num3+"\n";
        }
        if(N == 2){
            return num1+" "+num2+"\n"
                    +num1+" "+num3+"\n"
                    +num2+" "+num3+"\n";
        }
        return getHanoiPath(N-1, num1, num3, num2)
                +num1+" "+num3+"\n"
                +getHanoiPath(N-1, num2, num1, num3);
    }
}

 

 

(수정) StringBuilder를 쓰고 싶었는데, return값때문에 못쓰고 있었다. 생각해보니 굳이 반환값이 존재할 이유가 없었다.

868ms ->  316ms

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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());
        sb.append(countHanoiMove(N)).append("\n");
        getHanoiPath(N,1,2,3);
        System.out.println(sb);
    }
    static int countHanoiMove(int N){
        if(N == 1) return 1;
        if(N == 2) return 3;
        return 2* countHanoiMove(N-1)+1;
    }
    static void getHanoiPath(int N, int num1, int num2, int num3){
        if(N == 1){
            sb.append(num1).append(" ").append(num3).append("\n");
            return;
        }

        getHanoiPath(N-1, num1, num3, num2);
        sb.append(num1).append(" ").append(num3).append("\n");
        getHanoiPath(N-1, num2, num1, num3);
    }
}

구글링을 통해 하노이 탑을 옮기는 횟수가 수열로 나타내지길래 사용했더니 4ms 빨라졌다.

 

 

부족한 실력으로 푼거라 조언 항상 감사합니다.