99클럽 코테 스터디 7일차 TIL , 하노이의 탑

문제

풀이

입력 n이 주어지면 크기 n부터 1까지의 막대가 기둥(1)에 쌓여있다.

이 모든 막대를 기둥(3)으로 옮겨주면 된다.

여기서 제한 조건은 한 번에 하나의 막대만 옮길 수 있고 작은 막대 위에 큰 막대를 놓을 수 없다.

 

우리는 3번의 위치로 모든 막대를 옮겨야 하는데 가장 큰 막대가 아래에 있어야 하므로 3번에 가장 큰 막대를 먼저 넣어줘야 한다. 그리고 그 막대는 더 이상 움직이지 않는다.

 

n=1일 경우에는 기둥(1)에서 기둥(3)으로 옮겨주면 된다. 1회

 

n=2일 경우에는 첫 막대를 기둥(1)에서 기둥(2)로 옮겨주고, 크기가 2인 막대를 기둥(1)에서 기둥(3)으로 옮겨주고, 기둥(2)에서 기둥(3)으로 막대를 옮겨준다. 3회 (이후부터 기둥은 (번호)로 표시)

 

n=3일 경우에 (1)->(3) (1)->(2) (3)->(2) 의 과정을 거치면 이후에는 가장 큰 막대를 3번의 위치로 옮겨주면 된다. 위에서 설명한 대로 그 막대는 더 이상 움직이지 않는다. 그렇게 되면 두 개의 막대를 3번으로 옮기는 작업과 같다.

 

n=4일 경우에도 (1)->(2) (1)->(3) (2)->(3) (1)->(2) (3)->(1) (3)->(2) (1)->(2) 이렇게 되면 위와 같이 세개의 막대는 2번 기둥에 있으므로 가장 큰 막대를 1번에서 3번으로 옮겨주기만 하면 된다.

 

제출 1 - 정답

import java.util.*;
class Solution {
    private final List<int[]> list = new ArrayList<>();
    
    public int[][] solution(int n) {
        hanoiTower(n, 1, 2, 3);	//재귀시작
        int totalCount = (int)Math.pow(2,n)-1;	//총량
        
        int[][] answer = new int[totalCount][2];
        for(int i=0;i<totalCount;i++){
            int[] arr = list.get(i);
            answer[i] = arr;
        }
        
        return answer;
    }
    public void hanoiTower(int n, int start, int mid, int end){
        if(n == 1){	//n==1일 경우 시작점에서 end로 옮겨주기
            list.add(new int[]{start, end});
            return;
        }
        else{
            hanoiTower(n-1, start, end, mid);	// mid로 옮겨주기
            list.add(new int[]{start, end});	//list 추가
            hanoiTower(n-1, mid, start, end);	//mid에서 end로 옮겨주기
        }
    }
}

 

 

TIL

• 너무너무 어려웠다. 규칙을 찾는 과정, 점화식을 도출하는 과정이 어려웠다. 실제로 푼 시간보다 더욱 많이 걸렸다.
• 문제를 해석하는 능력이 잘 길러지지 않는 것으로 보여, 이와 비슷한 문제를 반복적으로 풀 필요성을 느꼈다.