백준 5904번 Moo 게임 C++

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

 

 

moo 문자열을 간단하게 숫자로 나타내 보겠다.

moo는 3, mooo는 4, mooooo는 5 이런 식으로 사용할 것이다.

moo 수열은 3 -> 3 4 3 -> 3 4 3 5 3 4 3 이런 식으로 증가하게 된다.

 

n을 입력받아서 n이 수열의 길이보다 크다면 수열의 길이를 규칙에 맞춰서 늘리고,

n이 수열의 길이보다 작다면 n의 값을 재조정하고 수열의 길이를 축소해가면서 문제를 해결하였다.

 

처음에는 직접 수열을 구현해보았는데, 그런 식으로 문제를 풀면 메모리 초과가 난다.

따라서 규칙에 맞춰서 특정 위치의 문자를 구하는 식으로 문제를 해결해야 한다.

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

void solve(int num, int length, int middle) {
	if (num <= 3) {
		if (num == 1) {
			cout << 'm';
		}
		else {
			cout << 'o';
		}
		return;
	}
	if (num == length) {
		cout << 'o';
		return;
	}
	if (num > length) {
		if (num - length <= middle + 1) {
			if (num - length == 1) {
				cout << 'm';
			}
			else {
				cout << 'o';
			}
			return;
		}
		length = 2 * length + middle + 1;
		solve(num, length, middle + 1);
	}
	else {
		length = (length - middle) / 2;
		if (num <= length) {
			solve(num, length, middle - 1);
		}
		else {
			if (num - length <= middle) {
				if (num - length == 1) {
					cout << 'm';
				}
				else {
					cout << 'o';
				}
				return;
			}
			num = num - (length + middle);
			solve(num, length, middle - 1);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;
	solve(n, 3, 3);
};