[백준 5904번] [분할 정복/ 재귀] Moo 게임

Moo(n)를 구성하는 것은 Moo(n-1)에 의해 결정된다는 것을 활용해서 분할 정복 아이디어가 떠올랐으면 충분하다.

 

다만, 이 문제에서 해당 자릿수를 만족하는 알파벳을 구하는 것이 핵심이므로

바로 분할정복으로 들어가지말고, Moo(n)에 해당하는 자릿수를 구해서 어느 Moo value 자리에 의해 알파벳이 결정되는지 판단해주면 된다.

 

Moo(n)은 Moo(n- 1) + M + o * (n + 2) + Moo(n - 1)이므로

해당 자릿수가 앞의 Moo(n - 1) 위치인지, 가운데인지, 뒤의 Moo(n - 1) 위치에 있는지 판단해주면 된다.

만약 앞 뒤의 Moo(n - 1)에 존재하는 경우, 분할정복으로 처리해주면 되고 가운데에 있는 경우는 맨 처음 자리만 빼고는 o을 출력해주면 된다.

 

다만, Base는 n이 0일때로 설정해주면 된다.(더이상 쪼갤 수 없는 element이다.)

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
int n;
vector<int> dp;

void find_value(int num, int n){
    if(n == 0){
        if(num == 1){
            cout << "m\n";
            return;
        }
        else{
            cout << "o\n";
            return;
        }
    }
    if(num <= dp[n - 1]){
        find_value(num, n - 1);

    }
    else if(dp[n - 1] < num && num <= dp[n - 1] + n + 2){
        if(num - dp[n - 1] == 1){
            cout << "m\n";
            return;
        }
        else{
            cout << "o\n";
            return;
        }

    }
    else{
        find_value(num - dp[n - 1] - n - 3, n - 1);
    }
}

int main(void){
    cin >> n;
    dp.push_back(3);
    int count = 1;
    while(true){
        int add_value =  count + 3;
        int increase_value = dp[count - 1] * 2 + add_value;
        dp.push_back(increase_value);
        count++;
        if(increase_value >= n) break;
    }
    find_value(n, dp.size() - 1);
}