문제 개요

문제: Moo 게임

분류: 분할 정복, 재귀

난이도: 골드5

문제 풀이

Moo 수열은 세 가지 부분으로 나눌 수 있다.

1. S(k-1)
2. o가 k+2개인 수열
3. S(k-1)

N번째 글자는 길이가 N 이상인 Moo 수열 중 가장 짧은 Moo 수열의 세 가지 부분 중 하나에 속해있다.

직접 Moo 수열을 구할 수도 있겠지만, N의 최대 범위가 크기 때문에 전체 Moo 수열을 변수에 담을 수 없거나 많은 재귀적 호출로 인해 메모리 초과가 발생한다.

따라서 수열의 길이를 바탕으로 N번째 글자를 구한다.

• totalLength : 현재 수열 S(k)의 길이
• temp : o가 k+2개인 수열의 길이
• prevLength : 이전 수열 S(k-1)의 길이

위 세 값을 이용하면 N이 앞쪽의 S(k-1)에 속해있는지, 중간의 o가 k+2개인 수열에 속해있는지, 뒤쪽의 S(k-1)에 속해있는지 판단할 수 있다.

반복문을 통해 N번째 글자를 찾을 때까지 아래 과정을 반복한다.

N이 앞쪽의 S(k-1) 수열에 해당한다면 totalLength를 prevLength로 바꾸고 temp 또한 1만큼 길이를 줄인다. 즉 S(k-1) 수열만 남겨두고 그 속에서 다시 세 부분으로 나누어 N이 어디 속해있는지를 검사하는 것이다.

N이 뒤쪽의 S(k-1) 수열에 해당하는 경우도 동일하다. 단, 이 경우 앞쪽의 S(k-1) 수열의 길이와 o가 k+2개인 수열의 길이를 N에서 빼야 한다.

N이 중간의 o가 k+2개인 수열에 해당한다면 가장 첫 번째 원소만 “m”이고 나머지는 “o”이므로 N에서 S(k-1)의 길이만큼을 뺐을 때 1인 경우 “m”을, 그렇지 않은 경우 “o”를 출력하고 반복문을 종료한다.

코드

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

const solution = (N) => {
  let totalLength = 0;
  let temp = 3; // o가 k+2개인 수열의 길이

  while (1) {
    totalLength = totalLength * 2 + temp;
    if (totalLength >= N) break;
    temp++;
  }

  while (1) {
    let prevLength = ~~((totalLength - temp) / 2);

    if (N <= prevLength) {
      // N이 앞쪽 수열에 해당하는 경우
      totalLength = prevLength;
      temp--;
    } else if (prevLength < N && N <= prevLength + temp) {
      // N이 o가 k+2개인 수열에 해당하는 경우
      if (N - prevLength === 1) console.log("m");
      else console.log("o");
      break;
    } else if (prevLength + temp < N) {
      // N이 뒤쪽 수열에 해당하는 경우
      N -= prevLength + temp;
      totalLength = prevLength;
      temp--;
    }
  }
};

solution(N);