[알고리즘 - 재귀] 피보나치 수열

하노이탑 문제 - 프로그래머스

처음에 계속 종이에 기둥 3개를 그려놓고 n=3, n=4, n=5, ... 이렇게 계속해서 작성해보았다. 내가 찾은 규칙은 이러하다.
1. n이 짝수인 경우 처음시작(n=1)은 두번째 기둥이고 이후에는 세번째 기둥, 두번째 기둥을 번갈아간다.
n이 홀수인 경우 처음시작(n=1)은 세번째 기둥이고 이후에는 두번째 기둥, 세번째 기둥을 번갈아간다.
2. 목표한 n이 세번째 기둥에 가기위해서는 첫번째 기둥에 마지막 가장 큰 원판이 있고 나머지 원판은 두번째 기둥에 차례대로 쌓아져있어야 한다.

import java.util.*;
class Move{
    int a;
    int b;
    public Move(int a, int b){
        this.a = a;
        this.b = b;
    }
}
class Tower{
     List<Integer>list = new ArrayList<>();
     int posi;
    
    public Tower(List<Integer> list, int posi){
        this.list = list;
        this.posi = posi;
    }
}
class Solution {
    public static List <Integer> listA = new ArrayList<>();
    public static List <Integer> listB = new ArrayList<>();
    public static List <Integer> listC = new ArrayList<>();
    public static int target = 1, posi = 2;
    public static int max;
    public static List<Move> answer = new ArrayList<>();
    
    public int[][] solution(int n) {
        
        
        for(int i=n;i>=1;i--){
            listA.add(i);
        }
        
        max = n;
        
        if(n%2 == 1){
            posi = 3;
            honoi(new Tower(listA,1), new Tower(listC, 3), new Tower(listB, 2));
        }else{
            honoi(new Tower(listA,1), new Tower(listB, 2), new Tower(listC, 3));
        }
        
        int ans[][] = new int[answer.size()][2];
        for(int i = 0;i<answer.size();i++){
            ans[i][0] = answer.get(i).a;
            ans[i][1] = answer.get(i).b;
        }
        return ans;
    }
    public static void honoi(Tower listNow, Tower listTarget, Tower listHelp){
        int a = listNow.list.get(0);
        listNow.list.remove(0);
        
        if(a > listTarget.list.get(0)) return;
        
        listTarget.list.add(0, a);
        
        if(listTarget.list.get(0) == target && listTarget.posi == posi){
            target++;
            if(posi == 2) posi = 3;
            else posi = 2;
            answer.add(new Move(listNow.posi, listTarget.posi));
            
            if(target > max) return;
        }
        
        honoi(listTarget, listHelp, listNow);
        honoi(listHelp, listTarget, listNow);
        
        
        
        
    }
}

여기서 핵심은 원판이 어디에서(from) 어디로(to)갈지만 리턴해주면 된다는 것이다.

소스코드

import java.io.*;
import java.util.*;

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    
    void hanoi(int numOfCircle, int from, int to, int other){
        if(numOfCircle == 0) return;
        hanoi(numOfCircle-1,from, other,to);
        List<Integer> l = new ArrayList<>();
        l.add(from); l.add(to);
        res.add(l);
        hanoi(numOfCircle-1,other, to,from);
    }
    
    public int[][] solution(int n) {
        hanoi(n, 1, 3, 2);
        int[][] answer = new int[res.size()][2];
        for(int i=0;i<res.size();i++){
            for(int j=0;j<2;j++){
                answer[i][j] = res.get(i).get(j);
            }
        }
        return answer;
    }
}

소스코드2

import java.util.*;

class Solution {
    
    ArrayList<int[]> seq;
    public int[][] solution(int n) {
        seq = new ArrayList<>();
        
        hanoi(n, 1, 3, 2);
        
        int[][] answer = new int[seq.size()][2];
        for(int i = 0 ; i < seq.size() ; ++i){
            int[] cmd = seq.get(i);
            answer[i][0] = cmd[0];
            answer[i][1] = cmd[1];  
        }
        
        return answer;
    }
    
    private void hanoi(int n, int from, int to, int via){
        int[] move = {from, to};
        
        if(n == 1) {
            seq.add(move);
        } else {
            hanoi(n - 1, from, via, to);
            seq.add(move);
            hanoi(n - 1, via, to, from);   
        }
    }
}