[알고리즘] 가지는 치지만 분할은 어려운 사람.

moo..

moo게임을 풀어보자

 

이문제는 재귀다.

 

const input = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .trim();

const N = Number(input);

function makeMoo(n) {
  if (n === 1) return "moo";
  const prev = makeMoo(n - 1);
  return prev + "m" + "o".repeat(n + 2) + prev;
}
const str = makeMoo(N);
console.log(str[N]);

 

재귀를 위풍당당 야무지게 돌렸지만

재귀는 조심해야해..

 

---

🚨 하지만 재귀에는 함정이 있어요!

문제는... S(n)의 길이가 기하급수적으로 커진다는 점입니다.

예를 들어 S(10)을 만들면 거의 수십억 글자가 되기 때문에, 이 코드는 메모리도 터지고 시간도 오래 걸립니다.

 

---

❓그럼 어떻게 하면 좋을까요?

바로바로 분할정복입니다!

 

---

🧠 분할정복이란?

문제를 작은 문제로 나누고(Divide),
각각 해결한 뒤 정복(Conquer) 하여 전체 문제를 푸는 방법입니다.

 

Moo 게임에서는 S(n)이 항상

S(n) = S(n - 1) + "m" + "o".repeat(n + 2) + S(n - 1)

 

처럼 좌-중앙-우 구조로 반복되니까,

 

"내가 찾는 글자가 어느 쪽에 있는지"만 판단하면
실제로 문자열을 만들 필요가 없습니다!

 

---

🧠 문자열의 길이를 먼저 계산해보자

function getLength(k) {
  if (k === 0) return 3; // S(0) = "moo"
  return 2 * getLength(k - 1) + k + 3;
}

 

getLength(k)는 S(k)의 총 길이를 구해줍니다.

---

🧭 위치만 추적해서 찾기!

function findMoo(k, n) {
  if (k === 0) return "moo"[n - 1];

  const left = getLength(k - 1);
  const middle = k + 3;

  if (n <= left) {
    return findMoo(k - 1, n); // 왼쪽
  } else if (n <= left + middle) {
    return n === left + 1 ? "m" : "o"; // 가운데
  } else {
    return findMoo(k - 1, n - left - middle); // 오른쪽
  }
}

 

N이 어디에 속하는지만 판단해서 필요한 부분만 재귀!

---

🧩 전체 코드 (최적화 버전)

const input = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .trim();

const N = Number(input);

function getLength(k) {
  if (k === 0) return 3;
  return 2 * getLength(k - 1) + k + 3;
}

function findMoo(k, n) {
  if (k === 0) return "moo"[n - 1];

  const left = getLength(k - 1);
  const middle = k + 3;

  if (n <= left) return findMoo(k - 1, n);
  else if (n <= left + middle) return n === left + 1 ? "m" : "o";
  else return findMoo(k - 1, n - left - middle);
}

// 최소한의 k 찾기
let k = 0;
while (getLength(k) < N) k++;

console.log(findMoo(k, N));

 

---

🧠 정리!

방법 특징 결과

재귀로 문자열 생성	실제 문자열을 만들어버림	❌ 비효율적, 메모리 초과
분할정복	위치만 추적해서 해결	✅ 효율적, 깔끔함

 

 

 

moo !