문제 출처
나의 풀이
다른 풀이
dp 풀이
예를 들어 n=3일 때,
from에 123이 들어 있는 상태에서 시작한다.
이 123을 to에 123 그대로 넣으면 완성이다.
문제를 작게 분할하는 게 중요한데,
가장 아래 쌓여 있는 3이 to로 가기 위해서 어떻게 해야 할지를 문제로 설정해야 한다. 가장 아래 쌓여 있는 3이 to로 가려면?
원판이 1개면 바로 옮겨주면 된다.
원판이 2개 이상이면,
result = result.concat(dp(n - 1, from, to, mid));
⇒ from 기둥에 있는 n개의 원판 중 n-1개를 mid 기둥으로 옮긴다. (단순히 mid에만 쌓을 수 없으므로 to 기둥을 사용해야 한다)
result.push([from, to]);
⇒ from 기둥에 마지막으로 남아 있는 n번 원판을 to 기둥으로 옮긴다.
result = result.concat(dp(n - 1, mid, from, to));
⇒ mid 기둥에 있는 n-1개의 원판을 to 기둥으로 옮긴다 (마찬가지로 단순히 to에만 쌓을 수 없으므로 from 기둥을 활용해야 한다. 단순히 번호가 높은 원판을 위에 쌓을 수 없으므로)
dp(3, 1,2,3)이면
dp(2, 1,2,3)가 return 되는 시점까지가 mid에 12를 넣는 과정이고,
그리고 나서 3을 to 기둥에 넣고 dp(3, 1,2,3)이 return 되면서 12도 3위에 쌓이게 되고 종료된다.
from mid to
123
인 상황에서, 위에 있는 1을 to로 옮긴다. [1,3]
dp(1, 1,3,2)가 리턴되고 result에 병합된 후
n=2에서 result.push([1,2])를 한다. [[1,3], [1,2]]
그리고 다시 dp(1, 3, 1, 2)를 호출하고 return 되면서
n=3일 때로 돌아오고 나서
result = result.concat(dp(2, from, to, mid));에서
[[1,3], [1,2], [3,2]]가 된 상태에서
result.push([1,3])으로 3을 to기둥으로 옮긴다. [[1,3], [1,2], [3,2], [1,3]]
...
이렇게 반복하면 된다.
...
왜 이렇게 하냐면,
123이 from 기둥에 있을 때 단순하게 12를 mid에 21로 쌓으면 편하겠지만,
문제의 조건에서 2가 1 위에 있으면 안 되므로
아예 1를 가장 끝(to기둥)에 넣고 ([1,3])
2를 mid 기둥에 넣고 [1,2]
to기둥에 있는 1을 다시 mid 기둥으로 가져오면 ([3,2])
(만약에 n이 더 크면 to 기둥과 mid 기둥에 번갈아가면서 뿌린 다음에, 다시 번갈아가면서 수거하는 식으로 mid 기둥에 쌓는다. 결과적으로 n-1 원판이 mid 기둥의 제일 하단에 쌓여야 한다.)
3은 from 기둥에 있는 상태에서 mid 기둥에 12가 쌓여있게 된다.
그럼 이 상태에서 3을 to 기둥으로 옮기고 mid에 있는 12를 똑같은 방식으로 to기둥으로 옮겨오면 끝난다.
즉,
dp(n)이면 n번째 원판을 가장 끝에 배치하는 코드가 되고.
dp(n-1)이 return되면서 n번째 원판을 가장 끝에 배치할 수 있게 1~n-1까지의 원판이 mid에 쌓이게 되는 상황이 된다.
dp(n)에서
result.push([from, to]); 전까지 1~n-1 원판을 mid에 배치하고
result.push([from, to]);에서 결국 n번째 원판을 끝에 배치하고,
그 후에 1~n-1 원판을 그 위에 쌓는다.
function dp(n, from, mid, to) {
if(n == 1)
return [[from,to]];
let result = [];
// 빈자리에 1~(n-1) 원판들을 차례대로 배치하다가 mid에는 (n-1)이 배치되도록
result = result.concat(dp(n - 1, from, to, mid));
// n번째 원판을 끝에 배치하고
result.push([from, to]);
// 아래 재귀를 통해 mid에 1~(n-1)이 전부 쌓이고 마지막 기둥이 비워질 수 있게)
result = result.concat(dp(n - 1, mid, from, to));
return result;
}
function solution(n) {
return dp(n,1,2,3);
}
// console.log(solution(2)) // [[1, 2], [1, 3], [2, 3]]
console.log(solution(3))