백준 5904 Moo 게임

https://www.acmicpc.net/problem/5904

#include <iostream>

using namespace std;



string st = "moo";

void s(int n, int k, int len) {

    int nLen = len * 2 + k + 3;
    if (n <= 3) {
        cout << st[n - 1];
        return;
    }
    if (nLen < n) {
        s(n, k + 1, nLen);
    }
    else {
        if (n > len && n <= len + k + 3) {
            if (n - len != 1) {
                cout << "o";
            } else {
                cout << "m";
            }
            exit(0);
        } else {
            s(n - (len + k + 3), 1, 3);
        }
    }


}


int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;

    cin >> N;

    s(N, 1, 3);

    return 0;
}

1. 문제

길이가 무한대인 Moo 수열이 있다. 이는 다음과 같은 규칙을 따른다.

• s(0)=moo
• s(k)=s(k-1)+moo...o(o가 k-2개)+s(k-1)

n이 주어졌을 때, n번째 글자를 구하라.

2. 풀이

규칙 자체가 재귀적이므로 이를 사용하여 구현할 수 있다. 우선 해당 수열은 다음과 같이 주어져있다.

 중간의 moo...o의 길이는 k-1이므로 s(k-1)의 길이를 len이라 하고 s(k)의 길이를 nLen이라 하면

int nLen = len * 2 + k + 3;

이런 식이 나온다. 위를 부분별로 뜯어서 확인해보자. 우선 순서를 확인하기 위해 초기 moo 문자열을 선언해주었다.

string st = "moo";

if (n <= 3) {
    cout << st[n - 1];
    return;
}

n이 3 이하라면 s(0)에 해당하므로 위치에 따라 그대로 출력할 수 있다.

if (nLen < n) {
    s(n, k + 1, nLen);
}

s(k)의 길이가 구하고자 하는 위치의 idx보다 작다면 s(k+1)을 찾아 탐색해야 한다.

if (n > len && n <= len + k + 3) {
    if (n - len != 1) {
        cout << "o";
    } else {
        cout << "m";
    }
    exit(0);
}

n이 s(k-1)의 길이보다 길고, len+k+3 이하라면 이는 두 s(k-1) 사이에 있는 moo...o의 경우이다. n-len, 즉 첫번째 글자만 m이고 나머지는 o이므로 위와 같이 출력하고 프로그램을 종료한다.

else {
    s(n - (len + k + 3), 1, 3);
}

그 외의 경우 양쪽 모두 s(k-1)의 범위이다. 따라서 s(k-1)을 구하는 쪽으로 재귀를 호출한다.