[Algorithm] Dragoon Curve

const int MAX = 1000000000 + 1;

 

int length[51];

void precalc() {

length[0] = 1;

for(int i = 1 ; i < 51 ; i++) {

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

}

}

 

const string EXPAND_X = "X+YF";

const string EXPAND_Y = "FX-Y";

 

char expand(const string& dragoon, int generation, int skip) {

// 기저 사례

if(generation == 0) {

return dragoon[skip];

}

 

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

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

if(skip > length[generation])

skip -= length[generation];

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

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

else

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

else if(skip > 0) // 확장되지는 않지만 한칸 건너 뛰어야 하는 경우 (F,+,-)

--skip;

else // 답을 찾은 경우

return dragoon[i];

}

}

return "#";

}