AlgoSpot) DRAGON

문제 : https://algospot.com/judge/problem/read/DRAGON

DP를 이용해서 드래곤 커브의 부분 문자열을 출력하는 문제입니다.

문제에서 드래곤 커브의 세대는 최대 50이므로 크기 50의 int 배열을 이용해서 DP로 구현했습니다.

부분문자의 시작부터 하나씩 문자를 출력해나가는 함수입니다.

X나 Y를 N번 중첩한 길이를 length배열에 미리 저장해두고 불필요한 재귀를 줄여서 문제를 해결하면 됩니다.

그리고 문자열의 시작위치는 1000000000을 넘을수 없으므로 만약 중첩길이가 1000000000을 넘으면 1000000000으로 설정하면 overflow를 예방할 수 있습니다.

#include 

#include 
#include 
using namespace std;

const int MAX = 1000000000; // 최대 문자열의 길이
int gen_length[51]; // n번 치환시 길이
int n, p, l; 

const string Expand_X = "X+YF";
const string Expand_Y = "FX-Y";

void set_gen_length() {
	gen_length[0] = 1;

	for (int i = 1; i <= 50; i++) {
		gen_length[i] = min(MAX , 2 * gen_length[i - 1] + 2	);
	}

	return;
}

char Dragon_Curve(const string& str, int gen, int dest_idx) {
	if (gen == n) if (dest_idx < str.size()) return str[dest_idx]; // 목표한 세대까지 도달했을경우 해당하는 문자를 출력		
	
	
	for (int i = 0; i < str.size(); i++) {
		if (str[i] == 'X' || str[i] == 'Y') {
			if (dest_idx >= gen_length[n - gen]) dest_idx -= gen_length[n - gen]; // 남은 중첩길이보다 dest_idx가 클경우
			else if (str[i] == 'X') return Dragon_Curve(Expand_X, gen + 1, dest_idx);
			else return Dragon_Curve(Expand_Y, gen + 1, dest_idx);
		}
		else if (dest_idx > 0) --dest_idx; // F나 +, - 가나와서 확장 될게없지만 목표인덱스가 아닐경우
		else return str[i]; // 목표한 인덱스 일경우 그 문자를 리턴
	
	}

	return 'E'; // 어니에도 해당되지않으면 에러이므로 E를 출력해서 에러검출
}


int main() {
	std::ios::sync_with_stdio(false);
	int C;
	//freopen("text.txt", "r", stdin);
	cin >> C;
	set_gen_length();

	while (C--) { // 케이스 시작
		cin >> n >> p >> l; // 1 1 5
		
		char c;

		for (int i = 0; i < l; i++) {
			c = Dragon_Curve("FX", 0, p + i -1);

			if (c == 'E') { // c가 출력될시 에러
				cout << "Recursive Error" << endl;
				return 0;
			}

			cout << c;
		}
		cout << endl;
	}

	return 0;
}