[TIL] 20210615 - 항해 9일차

알고리즘 마라톤 2일 차.

오늘 공부한 것

BAEKJOON ONLINE JUDGE(BOJ)

오늘 알고리즘 커밋 바로가기

• 1436 영화감독 숌
• 2869 달팽이는 올라가고 싶다
• 1037 약수
• 2609 최대공약수와 최소공배수
• 10250 ACM 호텔
• 1929 소수구하기
• 11729 하노이 탑 이동 순서
• 11651 좌표 정렬하기 2

오늘의 어려움

하노이 탑 이동순서 는 머리를 쥐어 뜯으며 풀었다.
아예 감도 못잡겠다면 다른 풀이를 찾아볼텐데 감이 한 70%로 왔다가 가버리고 80%로 왔다가 가버리는 그런 일의 반복이었다.

마음을 가라앉히겠다며 원판이 네 개인 경우를 저렇게 그려보기도 했다.
(심지어 첫 상태를 1로 두어서 16번이 최소 숫자인지 알았다.)

이 문제가 특히나 어려웠던 것은 내가 재귀함수에 굉장히 약하기 때문이었다.

아직도 재귀함수는 한 번에 이해가 안되고 한참 봐야 아... 하고 이해한다.

그래서 이 문제를 풀어냈을 때의 즐거움이 잊히지 않는다.

let fs = require("fs");
let input = Number(fs.readFileSync("/dev/stdin").toString());

let result = "";
let count = 0;

function hanoi(start, mid, end, n) {
  if (n === 1) {
    result += start + " " + end + "\n";
    count++;
    return;
  }
  hanoi(start, end, mid, n - 1);
  hanoi(start, mid, end, 1);
  hanoi(mid, start, end, n - 1);
}

hanoi("1", "2", "3", input);

console.log(count);
console.log(result.trim());