[백준 5904] Moo 게임

문제 링크 => 5904번: Moo 게임 (acmicpc.net)

5904번: Moo 게임

---

재귀를 이용한 분할 정복문제이다.

 

이 문제는 다음과 같이 Moo 수열을 만들 수 있다.

 

S(0) = moo

 

S(1) = moo mooo moo

 

S(2) = moo mooo moo moooo moo mooo moo

 

...

 

S(k) = S(k - 1) moo ... o S(k - 1)  (o의 개수는 (k + 2) 개)

 

이런식으로 Moo 수열을 구할 수 있다.

 

근데 N 번째 글자를 구하기 위해서 S(k) 에 대한 문자열에 대해서 길이로 접근해서 해결하면 뭔가 쉽게 해결될 거 같다는 생각을 했다.

 

L(S(k)) = L(S(k - 1)) + L(moo...o) + L(S(k - 1))

            = 2 * L(S(k - 1)) + L(moo ... o)

            = 2 * L(S(k - 1)) + k + 3

 

따라서 L(S(k)) = 2 * L(S(k - 1)) + k + 3    라는 식을 구할 수 있다.

 

base case를 먼저 구하자.

 

k = 0 인 경우 => 'm' 를 출력k = 1, 2 인 경우 => 'o' 를 출력

 

그리고 L(S(k)) 를 이용하기 위해서 약간의 simulation 을 해보았다.

 

S(2) = moo mooo moo moooo moo mooo moo 에서 N = 11, 15, 20 인 경우를 살펴볼 것이다.

 

case 1 ) N = 11, 15 인 경우

 

- L(S(1)) = 2 * L(S(0)) + 4 = 2 * 3 + 4 = 10 이다.

  N 값이 10 보다 크므로 S(1) 에 포함하지 않는다.

 

- L(S(2)) = 2 * L(S(1)) + 5 = 2 * 10 + 5 = 25 이다.

  이 경우엔 S(2) 에 포함하는 경우이다.

 

N = 11 ) N - L(S(1)) = 11 - 10 = 1 이다. 즉, S(1) 다음에 연결될 문자 'm' 임으로 'm' 을 출력한다.

 

N = 15 ) N - L(S(1)) = 15 - 10 = 5 이다. 즉, S(1) 다음에 연결될 문자열 moooo 에서 'o' 임으로 'o' 를 출력한다.

 

case 1 을 일반화하면 다음과 같다.

 

1 <= N - L(S(k - 1)) <= k + 3 인 경우 1 이면 'm' 그 외에는 'o' 를 출력한다.

 

case 2 ) N = 20 인 경우

 

- L(S(1)) = 2 * L(S(0)) + 4 = 2 * 3 + 4 = 10 이다.

  N 값이 10 보다 크므로 S(1) 에 포함하지 않는다.

 

- L(S(2)) = 2 * L(S(1)) + 5 = 2 * 10 + 5 = 25 이다.

  이 경우엔 S(2) 에 포함하는 경우이다.

 

이때, N - L(S(k - 1)) = 20 - 10 = 10 > k + 3 이므로 case 1 은 성립하지 않는다.

 

이 경우에는 S(k - 1) 의 문자열에서 탐색을 시켜주도록 하기만 하면 그만이다.

 

따라서 N = N - L(S(k - 1)) - (k + 3) 으로 값을 초기화하고 또 다시 위와 같은 방법을 recursive 하게 하여 구하면 된다.

 

 

 

풀이 Code

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <algorithm>
#include <string.h>
#include <cstring>
#include <queue>
#include <stack>
#define endl '\n'
#define INF 1000000000
#define ll long long

using namespace std;

int N;

char mooGame(int x) {
	if (x == 1) return 'm';
	else if (x == 2 || x == 3) return 'o';

	int before = 0, len = 3, k = 1; // L(S(0)) = len = 3, k = 1 부터 시작
	while (1) {
		before = len; // L(S(k-1)) = before
		len = 2 * len + (k + 3); // L(S(k)) = 2L(S(k-1)) + (k + 3)
		if (len > x) {
			if (x - before >= 1 && x - before <= (k + 3)) {
				if (x - before == 1) return 'm';
				return 'o';
			}
			else {
				return mooGame(x - (before + k + 3));
			}
		}
		k++;
	}

}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> N;
	cout << mooGame(N);

	return 0;
}