단계별로 풀어보기(재귀 - 하노이 탑 이동 순서)

11729번: 하노이 탑 이동 순서 (acmicpc.net)

11729번: 하노이 탑 이동 순서

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

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 insertNumber = Integer.parseInt(br.readLine()),
        	moveCount = 1;
        
        String[] beforeArr, printArr;
        
        printArr = new String[1];
        
        printArr[0] = "1 3";
        
        for(int i = 1; i < insertNumber; i++) {
        	
        	beforeArr = printArr;
        	
        	
        	moveCount *= 2;
        	moveCount ++;
        	
        	printArr = new String[moveCount];
        	
        	for(int j = 0; j < beforeArr.length; j++) {
        		printArr[1 + (j*2)] = beforeArr[j];
        	}
        	
        	for(int j = 0; j < printArr.length; j +=2) {
        		
        		if(i % 2 == 0) {
        			if(j % 6 == 0) printArr[j] = "1 3";
        			if(j % 6 == 2) printArr[j] = "3 2";
        			if(j % 6 == 4) printArr[j] = "2 1";
        		}else {
        			if(j % 6 == 0) printArr[j] = "1 2";
        			if(j % 6 == 2) printArr[j] = "2 3";
        			if(j % 6 == 4) printArr[j] = "3 1";
        		}
        		
        	}
        	
        }
        
        bw.write(String.valueOf(moveCount) + "\n");
        
        for(int i = 0; i < printArr.length; i++) {
        	
        	bw.write(printArr[i] + "\n");
        	
        }
        
        bw.close();
        
    }
    
}

다른 시험공부한다고 한동안 안 풀고 있다가

 

심심해서 한 문제 풀러왔다.

 

전에 문제 대충 읽고 

 

하노이탑 원판 옮긴 횟수 구하는 식은 그냥 바로 구해놨는데

 

이동 순서는 바로 안 보여서 나중에 해야지 하고 다른 공부 했다.

 

대충 머리로 옮겨서 이동 순서를 적어놨는데

 

횟수는 그냥 * 2 하고 1 더해주면 됐다.

 

근데 저 순서가 문제였는데

 

오늘 조금 보니까

 

4, 5번째를 보면

 

4번째는 12 13 23

 

5번째는 13 12 32가

 

반복된다는 것을 알았는데

 

그 사이에 있는 것들을 수식화하기가 어려워서

 

다른 패턴을 찾아봤다.

 

String []에 순서 한 개(ex. 1 2)가 들어간다 가정하고

 

인덱스 번호가 1번부터 시작한다고 생각하면

 

다음 생성되는 배열에 자신의 인덱스 번호 2배에 해당되는 부분에

 

자신이 들어간다는 걸 알 수 있었고

 

남는 홀수 번의 배열에는

 

원판의 개수가 짝수 일 때는 12 23 31 순으로 들어가고

 

홀수 일 때는 13 32 21이 들어간다는 걸 확인할 수 있었다.

 

대충 생각하면 마지막 원판(n)이 13 되기 전에 2번에 n-1의 원판이 들어가 있어야 하는데

 

그 이동경로를 머리로 그려봤을 때 얼추 맞겠다 싶었다.

 

그래서 그냥 제출해보니 통과됐다.

 

별 찍기보다는 탑 쌓기가 쉬웠다 ㅋㅋㅋ

 

30분 정도 걸린 듯?