5904 Moo 게임

설명

Moo는 술자리에서 즐겁게 할 수 있는 게임이다. 이 게임은 Moo수열을 각 사람이 하나씩 순서대로 외치면 되는 게임이다.

Moo 수열은 길이가 무한대이며, 다음과 같이 생겼다.

m o o m o o o m o o m o o o o m o o m o o o m o o m o o o o o

Moo 수열은 다음과 같은 방법으로 재귀적으로 만들 수 있다. 먼저, S(0)을 길이가 3인 수열 "m o o"이라고 하자. 1보다 크거나 같은 모든 k에 대해서, S(k)는 S(k-1)과 o가 k+2개인 수열 "m o ... o" 와 S(k-1)을 합쳐서 만들 수 있다.

S(0) = "m o o"
S(1) = "m o o m o o o m o o"
S(2) = "m o o m o o o m o o m o o o o m o o m o o o m o o"

위와 같은 식으로 만들면, 길이가 무한대인 문자열을 만들 수 있으며, 그 수열을 Moo 수열이라고 한다.

N이 주어졌을 때, Moo 수열의 N번째 글자를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (1 ≤ N ≤ 10^9)이 주어진다.

출력

N번째 글자를 출력한다.

예시 입력

11

예시 출력

m

풀이 과정

해당 문제는 문자열의 점화식을 파악하는 것이 관건입니다. 문자열은 다음과 같은 패턴으로 변화합니다.

S(k) = S(k-1) + mo…oo + S(k-1)

이 문제의 입력은 10^9 까지 이므로 단순하게 접근해서는 절대 풀리지 않습니다.

예를 들어, String moo = moo + (mo…o) + moo; 이런식으로 10^9 개의 문자를 합치고, chatAt()으로 구한다는 방법은 먹히지 않습니다 (바보 같이 했다가,, 😢)

S(2) 문자열을 가져와 보겠습니다.

S(2) = "**m o o m o o o m o o** m o o o o **m o o m o o o m o o**"

핵심은 Moo 문자열은 다음과 같이 나눌 수 있다는 점입니다.

• 앞의 Moo = moomooomoo
• 중간의 Moo = moooo
• 뒤의 Moo = moomooomoo

이렇게 구역을 나누었을 때 좋은 점은 N이 어느 Moo에 위치해있느냐에 따라 해당 인덱스의 문자를 유추할 수 있다는 점입니다.

예를 들어, N이 중간 Moo 에 위치해 있다고 가정합니다.

중간 Moo는 맨 앞의 m을 제외한 나머지 문자는 전부 o입니다. 맨 앞의 m은 앞의 Moo의 바로 뒤 인덱스입니다. 앞 전의 점화식을 기억하시나요?

S(k) = S(k-1) + mo…oo + S(k-1)

우리는 S(k-1)을 가지고 S(k)를 구합니다. S(k-1)은 위에서 말하는 앞의 Moo 문자열이 되겠죠. 즉, 앞의 Moo 문자열의 길이를 이미 알고 있으니, 앞의 Moo 문자열 길이 +1에 해당하는 인덱스가 m 나머지가 o 입니다.

만약 앞의 Moo 혹은 뒤의 Moo에 N이 위치해 있다면 어떨까요? 재귀적으로 풀면 됩니다. 위의 예제를 이어 설명해보면 앞의 Moo 인 moomooomoo 또한 다음과 같이 나눌 수 있습니다.

• 앞의 Moo = moo
• 중간의 Moo = mooo
• 뒤의 Moo = moo

이 과정에서 N의 위치를 파악하여 위와 동일하게 계산을 이어나가면 됩니다.

최종 코드

import java.util.Scanner;

public class _5904 {

    static int N;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();

        // Initialization
        int length = 3;
        int prev = 3;
        int k = 0;

        //  n의 범위를 구해주기
        while (length < N) {
            k++;
            prev = length;
            length = 2 * prev + (1 + 2 + k); // S(K-1) * 2 + (moo...o)
        }

        Moo(length, k);
    }

    private static void Moo(int length, int k) {
        int prev = (length - (1 + 2 + k)) / 2; // 중간을 제외한 moo 크기를 구함
        if (k == 0) {
            if (N == 1) {
                System.out.print("m");
                return;
            } else {
                System.out.print("o");
                return;
            }
        }
        if (N <= prev) {
            Moo(prev, k - 1);
        } else if (prev + 1 <= N && N < prev + (1 + 2 + k)) { // prev + (moo...o)
            if (prev + 1 == N) {
                System.out.print('m');
            } else {
                System.out.print('o');
            }
        } else { // 앞 쪽에 있거나 뒤 쪽에 있는 경우
            N -= (prev + (1 + 2 + k));
            Moo(prev, k - 1);
        }
    }
}