백준 Gold 5 Moo 게임

Moo 게임 (백준 Gold 5)

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

재귀인줄 알았는데 풀고 나니
분할 정복 알고리즘 이었다

무한한 Moo 수열에서
주어지는 n 번째의 문자가
‘m’인지 ‘o’인지를 구하는 문제

• Moo 수열?
  S(0) = “moo”
  S(N) = S(N-1) + “moo” + ‘o’ * n - 1 + S(N-1)
  

첫 제출과 틀린 이유

#include<iostream>
#include<vector>
#include<string>

using namespace std;

const string m = "moo";

string recur(vector<string>& mooD,int n, int nowCount)
{
	if (mooD[nowCount].size() > 0)
		return mooD[nowCount];

	string temp = m;
	for (int i = 0; i < nowCount; i++)
	{
		temp += 'o';
	}

	return mooD[nowCount] = recur(mooD,n,nowCount -1) + temp + recur(mooD, n, nowCount - 1);
}


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

	vector<string> mooD(n + 1);

	mooD[0] = m;

	int findIdx = 0;

	while (mooD[findIdx].size() < n)
	{
		findIdx++;
		recur(mooD, n, findIdx);
	}

	cout << mooD[findIdx][n - 1];

	return 0;
}

딱 보면 알겠지만
직접 문자열을 구한 후
재귀를 통해 그걸 저장하고
이후, n번째 문자를 출려하는 방식이다

그러나 지나치게 많은 메모리를 잡아 먹기에
메모리 초과가 발생하였다

n이 10^9 이상 들어올 수 있으며
이 때, vector와 string 모두 길어지기에
메모리 초과가 발생하는 것으로 보인다

새로운 풀이 방식

곰곰히 생각해본 결과 깨달은 것은

‘굳이 string을 안 만들어도 되겠다’ 였다

결국 구하고 싶은 것은 ‘n’번째 문자가
‘m’인지 ‘o’인지를 구하는 것이고
그에 따른 규칙이 주어져 있었다

따라서 풀이 방식을 다음과 같이 바꾸었다

• 실제 n이 속하는 수열의 step
  
• 이후 step 내부에서 n이 속하는 위치를 구하고
  n의 값을 추정
  

제출 코드

#include<iostream>
#include<vector>
#include<string>

using namespace std;

const char cv[2] = { 'm','o' };

void isM(vector<int>& sizes, int step, int n)
{
	if (step == 0)
	{
		if (n == 0)
			cout << cv[0];
		else
			cout << cv[1];

		return;
	}

	int nowC = sizes[step - 1];
	if (nowC > n)
	{
		isM(sizes, step - 1, n);
		return;
	}

	n -= nowC;

	int nowMooSize = 3 + step;
	if (nowMooSize > n)
	{
		if (n == 0)
			cout << cv[0];
		else
			cout << cv[1];

		return;
	}

	n -= nowMooSize;

	isM(sizes, step - 1, n);
}

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

	if (n < 3)
	{
		if (n == 0)
			cout << cv[0];
		else
			cout << cv[1];

		return 0;
	}

	vector<int> sizes;
	sizes.push_back(3);

	int startIdx = 1;

	while (true)
	{
		int nowSize = sizes[startIdx - 1] * 2 + 3 + startIdx;
		sizes.push_back(nowSize);

		if (nowSize > n)
			break;

		startIdx++;
	}


	isM(sizes, startIdx, n);

	return 0;
}

해설

먼저 while 문을 통하여 ‘단계’를 구한다
그것을 startIdx라는 변수에 담은 후
재귀용 함수에 넣어 수행

MOO(N) = MOO(N-1) + “moo..o” + MOO(N-1)
이므로 n이 어느 위치에 해당하는지를 파악한 후
값을 구하면 된다

• 만약 n이 첫번째 MOO(N-1)에 존재한다면
  그냥 그대로 step만 낮추어 재귀 돌린다
  그렇지 않으면 MOO(N-1)의 크기 만큼
  n에서 빼준다
  (탐색 범위에서 제외)
  

• “moo…o” 내부에 속한다면
  m과 o인지를 확실히 구분 가능하므로
  n이 0이라면 m, 아니면 o를 출력하고 종료
  아니라면 역시 그 크기만큼 n에서 빼준다
  

• 마지막이라면 step만 낮추고 재귀 돌려준다
  (이미 n에서 앞 범위를 제외했으므로)
  

n이 수열의 특정한 ‘범위’인지를 판단하고
그에 따라서 범위를 좁혀나가는 방식

점차 탐색 범위를 좁혀나가기에
‘분할 정복’보다는 ‘이분 탐색’ 같은 느낌이였으나
개념 상으로는 ‘분할 정복’이 맞긴 하는듯?

• 이분 탐색은 정렬과 같은 사전 준비가 필요
  
• 분할 정복은 결국 주어지는 값에 기반하여
  ‘범위’를 나누는 알고리즘 이기에 ‘분할 정복’이 맞는 듯 하다
  

결과

처음에는 꽤나 어렵다고 생각했으나
생각을 조금 바꾸니 다행히 충분히 풀만한 문제였다