백준 5904(Moo 게임) c++

문제

5904번: Moo 게임

S(0) = "moo"

S(1) = S(0) + mooo + S(0)

S(2) = S(1) + moooo + S(1)

...

위와 같은 moo 수열이 있습니다. 이 때 n이 주어지면, n번째 글자를 출력하면 되는 문제입니다.

moo수열은 무한대입니다. n <= 10억

저 수열의 규칙대로 글자 수가 10억짜리인 문자열을 만들어 n번째 인덱스를 출력하면 메모리 초과로 당연히 안됩니다.

위의 규칙을 보면 S(k) = S(k-1) + M+(k+2)*o + S(k-1) 인것을 알 수 있습니다.

잘 보면 S에 대한 3가지 구간이 있다는 것을 알 수 있습니다.

1. S(k-1) 구간

2. M + (k+2)*o 인 구간

3. S(k-1) 구간

만약 내가 찾고자 하는 n번째 글자가 S(2)에 있는 경우 그 글자는 무조건 2, 3번 구간에 있어야 합니다.

만약 1번 구간에 있다고 하면 S(2)가 아닌 S(1)에서 그 글자가 찾아질 것입니다.

이제 조건을 걸어줍니다.

만약 2번 구간에 있다면 첫 글자를 제외한 모두가 "o" 를 가리킬 것이고, 첫글자는 "m"을 가리킬 것입니다.

만약 3번 구간에 있다면 그 3번구간을 다시 분할 해서 S(0)이 될 때 까지 글자를 구하면 됩니다.

string ans = "moo";
int n;
int main(){
	cin >> n;
	moo(n, 0, ans.length());
}

이제 위에서 설명한 것은 코드로 구현하겠습니다.

void moo(int i, int step, int init){
	int idx = step + 1;
    if(i <= 3){ //더이상 분할이 불가능한 경우
    	cout<<ans[i-1];
        return;
    }
    if(init * 2 + idx + 3 < i) //내가 찾고 싶어하는 n번째 글자가 해당 S에서 찾지 못할 경우
    	moo(i, idx, init*2+idx+3); //문자열 늘려줌
    }
    else{ //내가 찾고 싶어하는 n번째 글자가 해당 S에서 찾을 수 있는 경우
    	if (i > init + idx + 3) //3번째 구간에 있는 경우
            moo(i - (init + idx + 3), 0, ans.length());
        else //두번째 구간에 있는 경우
        {
            if (i - init == 1) //두번째 구간은 첫글자를 제외한 나머지 글자는 무조건 o를 출력
            {
                cout << "m";
                return;
            }
            else
            {
                cout << "o";
                return;
            }
        }
   }
}

위의 코드를 읽어보면 됩니다.

---

전체 코드입니다.

#include <iostream>
#include <string>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <math.h>
#define INF 2000000000
using namespace std;
using ll = long long;
string ans = "moo";
void moo(int i, int step, int init);
int n;
int main()
{
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    cin >> n;

    moo(n, 0, ans.length());
    return 0;
}
void moo(int i, int step, int init)
{
    int idx = step + 1;
    if (i <= 3)
    {
        cout << ans[i - 1];
        return;
    }
    if (init * 2 + idx + 3 < i)
        moo(i, idx, init * 2 + idx + 3);
    else
    {
        if (i > init + idx + 3)
            moo(i - (init + idx + 3), 0, ans.length());
        else
        {
            if (i - init == 1)
            {
                cout << "m";
                return;
            }
            else
            {
                cout << "o";
                return;
            }
        }
    }
}