드래곤 커브

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

입력

입력의 첫 줄에는 테스트 케이스의 수 c (c <=50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 세 개의 정수로 드래곤 커브의 세대 n (0 <= n <= 50) , 그리고 p 와 l (1 <= p <= 1,000,000,000 , 1 <= l <= 50) 이 주어집니다. n세대의 드래곤 커브 문자열의 길이는 항상 p+l 이상이라고 가정해도 좋습니다.

출력

각 테스트케이스마다 한 줄에 n세대 드래곤 커브 문자열의 p번째 글자부터 l글자를 출력합니다.

코드 ( C++ ) 종만북 참조

#include <iostream>

#include <string>

#include <algorithm>

#include <vector>

#include <cassert>

using namespace std;

const int MAX = 1000000000 + 1;

//llength[i] = X나 Y를 i번 치환한 후의 길이

int length[51];

void precalc() {

length[0] = 1;

for (int i = 1; i <= 50; ++i)

length[i] = min(MAX, 2 * length[i - 1] + 2);

}

const string EXPAND_X = "X+YF";

const string EXPAND_Y = "FX-Y";

// dragonCurve를 generations 진화시킨 결과에서 skip번째 문자를 반환한다.

char expand(const string& dragonCurve, int generations, int skip)

{

if (generations == 0) {

assert(skip < dragonCurve.size());

return dragonCurve[skip];

}

for (int i = 0; i < dragonCurve.size(); ++i)

//문자열이 확장되는 경우

if (dragonCurve[i] == 'X' || dragonCurve[i] == 'Y') {

if (skip >= length[generations])

skip -= length[generations];

else if (dragonCurve[i] == 'X')

return expand(EXPAND_X, generations - 1, skip);

else

return expand(EXPAND_Y, generations - 1, skip);

}

//확장되진 않지만 건너뛰어야 할 경우

else if (skip > 0){

skip--;

}

// 답을 찾은 경우

else {

return dragonCurve[i];

}

return '#'; // 이 줄은 수행되지 않는다.

}

int main()

{

int C;

cin >> C;

while (C--) {

string s = "FX";

int n, p, l;

cin >> n >> p >> l;

precalc();

for (int skip = p - 1; skip < p + l - 1; ++skip)

{

char temp = expand(s, n, skip);

cout << temp;

}

cout << endl;

}

return 0;

}