[C/C++] BOJ 5904번 : Moo 게임

1. 문제

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

2. 풀이

분할정복 문제는 써보는 게 장땡 !
머리 굴리지말고 써보자

• S(0) = Moo
  → 3
• S(1) = Moo / Mooo / Moo
  → 3 * 2 + 4 = 10
• S(2) = MooMoooMoo / Moooo / MooMoooMoo
  → 10 * 2 + 5 = 25
• S(3) = MooMoooMooMooooMooMoooMoo / Mooooo / …
  → 25 * 2 + 6 = 56
  

규칙을 파악했으면 점화식을 써보자

• 길이
  L(k) = L(k-1) * 2 + (k + 3)
• S(k) = S(k-1) + 규칙 + S(k-1)
  두번째 구간 : N < L(k-1) + k + 3

3. 코드

//BOJ_5904 Moo 게임 [골드 5]
#include <bits/stdc++.h>
#include <iostream>

using namespace std;

int N;
string str = "moo";
void Moo(int depth, int length) {
    if (N <= 3) {
        cout << str[N - 1];
        return;
    }

    int nxt = length * 2 + depth + 3;
    if (N > nxt) { //찾을 수 없을 때
        Moo(depth + 1, nxt);
    } else {    //찾을 수 있을 때
        //가운데 구간
        if (N == length + 1) {
            cout << "m" << '\n';
            return;
        }
        else if (N <= length + depth + 3) {
            cout << "o" << '\n';
            return;
        }
        //S(k-1)구간
        else {
            N -= (length + depth + 3);
            Moo(1, 3);
        }
    }
}
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    cin >> N;
    Moo(1, 3);
}