[백준 5904] Moo 게임(C++)

📕문제

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번째 글자를 출력한다.

---

🔎문제해석

처음에는 무작정 재귀로 박치기했는데 

멸망했다..

생각해보면 당연한 건데 나는 처음에 문자열에다가 계속 추가해줬는데 최대의 크기가 10^9라 당연히 메모리 초과가 날 수밖에 없는 것.. 그렇게 해서 다음 접근한 게 글자 수의 규칙을 찾아서 해당 글자 수에 해당하는 글자를 뽑아내려고 했는데 이것도 규칙 찾다가 날밤 샐 거 같아서 포기하고 그냥 분할 정복을 하기로 했다.

Moo 게임에는 규칙이 있다.

S(0) = Moo

S(1) = MooMoooMoo

S(2) = MooMoooMooMooooMooMoooMoo

를 보면 알 수 있듯이 

S(k)= S(k-1) + M+ o*(k+2) + S(k-1)이라는 점을 알 수 있다. [단 k>=1]

 

S에 대한 3가지 구간이 있다.

• S(k-1)인 구간
• Moo 게임의 규칙인 M+o*(k+2)
• S(k-1)인 구간

S(0) = Moo

S(1) = MooMoooMoo

S(2) = MooMoooMooMooooMooMoooMoo

이렇게 3구간으로 나눠져 있다.

여기서 만약 내가 찾고자 하는 n번째 글자가 S(2)에 있는 경우 그 글자는 파란색 구간과 초록색 구간에 있어야 하는 것이 당연하다.

만약 빨간색 구간에 있다고 생각이 든다면 S(2)가 아닌 S(1)에서 그 글자가 찾아질 것이다.

이제 우리는 찾고자 하는 글자가 파란색 구간과 초록색 구간에 있다는 것을 알고 있으니 조건만 정해주면 된다.

만약 파란색 구간에 있다면 첫 글자를 제외한 모두가 "o"를 가리킬 것이고, 첫 글자는 "m"을 가르킬 것이다.

만약 초록색 구간에 있다면 그 초록색 구간을 다시 분할해서 [S(0)이 될 때까지)] 글자를 구하면 된다.

 

💻예시를 들어서 설명해보겠다.

만약 23번째 글자를 찾고 싶다고 가정할 때

S(0)은 3글자. S(1)은 10글자. S(2)는 25글자 

따라서 23번째 글자는 S(2)에 있고, 23은  빨간색 구간[S(1)] + 파란색 구간[2+3]보다 크기 때문에 초록색 구간인 것을 알 수 있다.

MooMoooMoo 

23번째 글자는 빨간색 부분이다.

다시 이 MooMoooMoo를 분할한다.

MooMoooMoo

우리가 찾고자 하는 하얀색 M은 또 초록색 구간에 있기에 또 분할을 한다.

Moo는 우리가 정한 최소 글자 수[3]이기에 여기서 M에 대한 index인 M을 출력하면 된다.

---

📃코드

/*
백준  골드5 5904 Moo게임
s(0)= moo  3  [0]
s(1)= moo /mooo /moo 10 [0,3]
s(2)= moo mooo moo / moooo /moo mooo moo 25  [0,3,7,10]
s(3)= moo mooo moo moooo moo mooo moo / mooooo / moo mooo moo moooo moo mooo moo 56
[0,3,7,10,15,18,22]
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int n;
string str = "moo";
void moo(int i, int step, int init);
int main()
{
    cin >> n;
    moo(n, 0, str.length());
    // S(k)= s(k-1)+k*2+1+s(k-1)
}
void moo(int i, int step, int init)
{
    int idx = step + 1;
    if (i <= 3)
    { //임계점. 더이상 분할이 불가능함. 초기 문자열은 "moo"이기에
        cout << str[i - 1];
        return;
    }
    if (init * 2 + idx + 3 < i) //만약 내가 찾고싶어하는 번째의 글자가 해당 step에서 만들지 못한다면 문자열을 늘려줌.
    {
        moo(i, idx, init * 2 + idx + 3);
    }
    else //만약 내가 찾고싶어하는 번째의 글자가 해당 step에서 찾을 수 있다면?
    {
        if (i > init) 
        {
            //규칙에 의하면 s(k)=s(k-1)+규칙+s(k-1)이다.
            if (i - init <= idx + 3)  //이 조건에 걸린다는 뜻은 규칙안에 있다는 뜻이다.
            { 
                if (i - init == 1)//규칙에 의하면 m ooo...이기에 첫글자를 제외한 나머지 글자는 무조건 o를 출력한다.
                {
                    cout << "m";
                    return;
                }
                else
                {
                    cout << "o";
                    return;
                }
            }
            else //규칙 뒤쪽이라는 뜻은 내가 찾고자 하는 글자가 s(k-1)안에 있다는 뜻이다.
            { 
                moo(i - (init + idx + 3), 0, str.length());
                //뒤쪽에 해당하는 글자수인 i-(init+idx+3)을 인자로 넣어주고, 다시 처음부터 탐색을 시작함.
            }
        }
    }
}

---

✔느낀 점

• 분할 정복은 손이 고생해야 한다!
• 머리로 하려고 하지 말고 일단 처음부터 규칙을 찾고 손으로 해보는 게 맞을 거 같다.
• 이 문제 어려웠다.. 
• 분할 정복은 확실히 많이 풀어봐야 할 것 같다.