[C++] 드래곤 커브 DRAGON

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

algospot.com :: DRAGON

해결: X

 

사실 드래곤 커브를 아는 것과 거의 상관이 없는 문제입니다.

https://en.wikipedia.org/wiki/Dragon_curve

Dragon curve - Wikipedia

 

0세대에 FX인 문자를

X는 X+FY로, Y는 FX-Y로 치환하며 n세대까지 늘인 문자열을 구해야 합니다.

n세대의 모든 문자열은 너무 길기 때문에 해당 문자열에서 p번째 글자부터 l글자만 출력하면 됩니다.

---

expand(s, gen) 함수는 주어진 드래곤 커브 s를 gen 세대만큼 진화?시켜서 출력합니다.

함수는 순차적으로 아래 과정을 수행합니다.

1. 남은 세대가 0이라면 s를 출력

2. 검사하는 문자가 X 또는 Y라면 해당하는 치환을 gen-1 세대만큼 진화(재귀)

3. 검사하는 문자가 X 또는 Y가 아니라면 출력

 

이제 전역에서 skip 변수를 추가해서 전체 커브에서 skip번째 문자만 출력되도록 하겠습니다.

skip번째부터 l글자 만큼 출력하고 싶다면 l번 호출하면 되겠네요.

진화 과정에서 만나는 X와 Y는 길이가 1이 아닙니다.

각 X, Y가 gen세대까지 진화해서 생성되는 길이만큼 skip을 감소해줍니다.

X와 Y 이외의 문자는 길이가 1입니다.

위 과정에서 skip이 0일 때의 문자만 출력해주면 됩니다.

 

만약 어떤 X, Y에서 만들어지는 커브의 길이가 skip보다 작다면,

그 X, Y를 실제로 진화시킬 필요가 없습니다.

X, Y를 gen 세대 진화했을 때 커브 길이를 안다면 skip에서 그만큼 빼주기만 해도 같은 효과지요.

 

X, Y를 0세대 진화한 길이는 1, 그 다음 세대부터 순차적으로 4, 10, 22...

아래는 커브 길이의 점화식입니다.

skip의 값은 최대 1e9입니다.

그 이상의 값을 처리하고 오버플로우도 막아줍시다.

 

이제 gen세대 진화의 길이를 알았으니 skip과 비교해서 재귀하거나 skip을 length[gen]만큼 감소하거나 중 선택합니다.

 

마지막으로 length를 사용하면서 정확히 출력해야 하는 재귀만 수행하게 되었습니다.

때문에 skip이 다른 부분 문제에서 영향을 받을 일이 없기 때문에 skip을 매개 변수로 사용해줍시다.

 

또 깔끔하게 출력이 아닌 문자를 return하는 식으로 바꿔줍시다,

---

코드

 

// X를 i세대만큼 진화시킨 커브의 길이
int length[SZ];
void precalc(){
    length[0] = 1;
    for(int i=1; i<=50; i++)
        length[i] = min((int)1e9+1, 2*length[i-1]+2);
}

// s를 gen세대만큼 진화시킨 커브의 skip번째 문자
char expand(const string& s, int gen, int skip){
    if(gen==0)return s[skip];
    
    int len = length[gen];
    for(int i=0; i<s.length(); i++){
        if(s[i]=='X' || s[i]=='Y'){
            string sub = s[i]=='X'?"X+YF":"FX-Y";
            if(skip<len) return expand(gen-1, skip, sub);
            else skip-=len;
        }
        else if(skip>0) skip--;
        else return s[i];
    }
    return '#';
}