문제

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

---

풀이

• S(0) = moo
• S(k) = S(k-1) + {m + o * (k+2)개} + S(k-1) (k >= 1)

👉 N번째 글자는? (N은 최대 10억)
👉 문자열 길이는 무한대 (무한 수열)

메모리 초과

단순 재귀

N이 최대 10억이기 때문에 아래와 같이 단순 재귀 호출로 S(k)를 구하고, N번째 글자가 무엇인지 출력하면 메모리 초과가 발생한다.

#include <iostream>
#include <string> 
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <set>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

string moo(int k) {
	if(k == 0){
		return "moo";
	}

	string str(k + 2, 'o');
	string mid = 'm' + str; 
	return moo(k - 1) + mid + moo(k - 1);
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n; 
	cin >> n;

	int k = 0;
	while(true){
		string curMoo = moo(k);
		int len = curMoo.size();
		
		if(len >= n){
			cout << curMoo[n - 1] << endl;
			break; 
		}

		k++; 
	}

	return 0;
}

DP

중복되는 부분 문제를 재귀 호출하여 시간/공간 복잡도가 커지는 것을 막기 위해 dp 테이블을 이용하여 메모이제이션 해봤다.

dp 테이블의 최대 크기를 잡기 위해 수열 길이의 규칙성을 파악해보자.

k	S(k) 길이
0	3 -> len(S(0))
1	3 + 4 + 3 = 10
2	10 + 5 + 10 = 25
	...
i	len(S(i - 1)) + { len(S(0)) + i } + len(S(i - 1))

위와 같은 규칙에 의하면, 수열 S(k)의 길이는 2 * len(S(k - 1)) + k + 3 이 된다.

N이 최대 10억이므로 수열의 N번째 문자가 무엇인지 구하려면, dp 테이블의 크기는 최대 30 정도로 잡아야 한다. (2^30 > 10억)

#include <iostream>
#include <string> 
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <set>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int MAX = 30;
string dp[MAX]; // 길이 1e9인 문자열까지 포함 가능

string moo(int k) {
	if(k == 0){
		return "moo";
	}

	if(dp[k] != "") return dp[k];
	
	string str(k + 2, 'o');
	string mid = 'm' + str;
	dp[k] = moo(k - 1) + mid + moo(k - 1);
	return dp[k];
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n; 
	cin >> n;

	int k = 0;
	while(true){
		string curMoo = moo(k);
		int len = curMoo.size();
		
		if(len >= n){
			cout << curMoo[n - 1] << endl;
			break; 
		}

		k++; 
	}

	return 0;
}

이 방법도 역시나 메모리 초과..!!!

분할 정복

재귀적 풀이

참고: https://jja2han.tistory.com/163

앞서 S(k)의 길이가 2 * len(S(k - 1)) + k + 3 임을 알아냈다.

• len(S(k-1)) -> prevLen (이전 수열의 길이)
• k + 3 -> midLen (가운데 구간의 길이)
• 2 * prevLen + midLen -> curLen (현재 수열의 길이)

이렇게 변수를 선언하여 아래와 같이 재귀적 풀이로 답을 구할 수 있다.

#include <iostream>
#include <string> 
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <set>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

string s0 = "moo";
int len0 = s0.length(); 

void moo(int n, int k, int prevLen){
	// 기저 조건 
	if(n <= 3) {
		cout << s0[n - 1];
		return;
	}

	int idx = k + 1; // idx >= 1 
	int midLen = idx + len0; 
	int curLen = 2 * prevLen + midLen; 

	// 현재 수열의 길이가 n보다 작으면 
	if(curLen < n) {
		// 다음 수열 생성
		moo(n, idx, curLen);
	}else{
		// 현재 수열에서 n번째 문자를 찾을 수 있는 경우 

		// 가운데 영역 
		if(n - prevLen <= midLen){
			if(n - prevLen == 1){
				cout << "m"; 
				return;
			}else{
				cout << "o";
				return; 
			}
		}else{
			// 뒤쪽 구간의 문자열 분할하기 
			moo(n - (prevLen + midLen), 0, s0.length());
		}
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n; 
	cin >> n;

	moo(n, 0, s0.length());

	return 0;
}

반복적 풀이

참고: https://programforlife.tistory.com/59

수열은 전혀 보지 않고 '길이'에만 집중한다.

세 개의 구간으로 나눠서 수열의 길이를 계속 쪼개다가 3 이하가 되면 현재 n의 값에 따라 m 또는 o 를 출력한다.

#include <iostream>
#include <string> 
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <set>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

int n;
string s0 = "moo";
int len0 = s0.length(); 

void solution() {
	int curLen = len0;
	int midLen = len0;

	// 현재 수열의 길이가 n보다 작으면 
	// n 이상이 될 때까지 길이 늘리기 
	while(curLen < n){
		curLen = 2 * curLen + ++midLen;
	}

	while(true){
		int prevLen = (curLen - midLen) / 2; 

		// 첫번째 구간 
		if(n <= prevLen){
			// 이전 수열의 길이로 분할 
			midLen--; 
			curLen = prevLen; 
		}
		// 세번째 구간 
		else if(n > prevLen + midLen){
			// 이전 수열 길이로 분할 
			n -= prevLen + midLen; 
			midLen--; 
			curLen = prevLen; 
		}
		else{ // 두번째 구간 
			n -= prevLen; 
			break; 
		}
	}

	if(n == 1){
		cout << "m";
	}else{
		cout << "o";
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;

	solution(); 

	return 0;
}

분할 정복 어렵다.... 기저 조건도 잘 잡아야 하고, 재귀 호출도 스택 오버플로우가 나지 않게 조심히 다뤄야 한다.