https://school.programmers.co.kr/learn/courses/30/lessons/12946
n = 1일때, 2 일때, 3일때 옮기는 순서를 적어 보았다
2 일때 순서들이 3일때 순서들 속에 있었다. 이 상태에서 내가 알 수 있는 규칙은
n이 1씩 증가할때 순서들 사이사이에 순서가 추가된다는것..
n=4 일때 15개가 되지 않을까 생각하고 또 적어보았다
저 초록색 부분에 순서를 알아내면 된다 그래서 직접 스프레드 시트에 또 적어보았다
n=3일때의 숫자를 참고해서 순서를 알아내려고 애썻다.
원반을 작은것부터 A, B, C, D로 적을 수 있었다. 초록색 부분을 채웠다
15번만에 옮길수있는것을 확인하였다 이제 규칙을 찾아보자
규칙을 찾으려고 한참 고민하다가 안풀려서;;
검색해봤는데 재귀로 풀면된다 하;;
난 왜 그림 처럼 뻗어나가는 패턴을 못본것일까
봤다해도 어떻게 저렇게 자녀의 값이 만들어 지는지 발견 못했을거 같긴하다
풀이코드를 보니 왜 저렇게 순서가 만들어지는지 이해가 되었다
1, 2, 3 중에서 비어있는 녀석을 활용하면 순서가 만들어진다
예를들어 부모가 1-3 인경우 자녀를 만들어보자 비어있는 숫자 2를사용해서 1-2, 2-3 을 만들면 된다
from(1), empty(2), to(3)
from - empty, empty - to 로 숫자를 만들면 된다
부모가 1-2 인경우 비어있는 숫자3을 활용해서 1-3, 3-2 을 만들면 된다.
from(1), empty(3), to(2)
from - empty, empty - to 로 숫자를 만들면 된다
n이 4일때 까지의 경우를 만들어봤지만 왜 저렇게 만들어지는지 패턴을 찾는게 어렵다;;
class Solution {
static int N;
static int idx = 0;
public int[][] solution(int n) {
int len = (int)Math.pow(2, n)-1;
int[][] answer = new int[len][2];
N = n;
recur(1, 3, 0, answer);
return answer;
}
public static void recur(int from, int to, int depth, int[][] answer)
{
if(depth == N)
{
return;
}
int empty = 6 - from - to;
recur(from, empty, depth+1, answer);
answer[idx][0] = from;
answer[idx][1] = to;
idx++;
recur(empty, to, depth+1, answer);
}
}