[C++] 백준 5904번: Moo 게임

문제 링크

5904번: Moo 게임

문제 요약

Moo 수열에서, S(0)는 "moo"이고, S(k)는 S(k-1) + ("m" + "o" * (k+2)) + S(k-1)을 통해서 만들 수 있다. 이때 Moo 수열의 N번째 글자를 구하는 프로그램을 작성해야 한다.

접근 방법

초기 접근 시에는 Moo 수열을 m을 기준으로 끊어서 갯수를 저장하는 방식으로 코드를 작성했는데 MLE를 받았습니다.

MLE를 받은 코드

#include <bits/stdc++.h>

using namespace std;

int main(void) {
	int n;
	cin >> n;

	if (n == 1) {
		cout << 'm' << '\n';
		return 0;
	}

	int sz = 3;
	vector<int> v;
	v.push_back(3);
	for (int i = 4; sz < n; i++) {
		int len = v.size();
		v.push_back(i);
		for (int j = 0; j < len; j++)
			v.push_back(v[j]);
		
		sz *= 2;
		sz += i;
	}

	int sum = 0;
	for (auto& i : v) {
		sum += i;

		if (sum + 1 == n) {
			cout << 'm' << '\n';
			return 0;
		}
	}

	cout << 'o' << '\n';
	return 0;
}

저장되는 수들이 의외로 크지가 않기 때문에 최대 10억인 N까지 대응해 저장하면 벡터의 크기가 매우 커질 수밖에 없습니다. 따라서 MLE를 받았습니다.

중간에, 1과 0 비트를 이용해서 'm'과 ,'o'를 저장 해볼까 고민하다가 너무 복잡한 풀이가 될 것 같다는 생각을 했습니다. 그래서 결국 재귀호출을 통해서 푸는 아이디어를 떠올려봤습니다.

1. 길이가 N보다 크거나 같으면서 가장 작은 Moo 수열의 크기를 구합니다.
2. 해당 Moo 수열을 앞 부분, 새로 추가된 중앙 부분, 뒷 부분으로 나눕니다.
3. N의 위치에 따라서 구간을 선택해서 재귀호출합니다.

만약 현재 구간의 크기가 3이 되거나, 중앙 부분이 선택된다면 결과를 출력하고 종료합니다. 종료할 때를 기준으로, N이 구간의 맨 처음에 온다면 'm'을 출력하고, 그 외의 경우에는 'o'를 출력하면 됩니다.

코드

#include <bits/stdc++.h>

using namespace std;

void func(int s, int e, int mid_len, int n) {
	if (e - s + 1 == 3) {
		cout << (n == s ? 'm' : 'o') << '\n';
		exit(0);
	}

	int p1 = (e - s + 1 - mid_len) / 2 + s - 1;
	int p2 = p1 + mid_len + 1;

	if (n <= p1)
		func(s, p1, mid_len - 1, n);
	else if (n >= p2)
		func(p2, e, mid_len - 1, n);
	else {
		cout << (n == p1 + 1 ? 'm' : 'o') << '\n';
		exit(0);
	}
}

int main(void) {
	int n;
	cin >> n;

	int sz = 0, i = 0;
	for (i = 0; sz < n; i++) {
		sz *= 2;
		sz += (i + 3);
	}

	func(1, sz, i + 2, n);
	return 0;
}