[알고스팟] 드래곤 커브

문제 링크

드래곤 커브

• 문제
• 답안 제출
• 통계

문제 정보

• • 문제 ID
  • 시간 제한
  • 메모리 제한
  • 제출 횟수
  • 정답 횟수 (비율)
• • DRAGON
  • 2000ms
  • 65536kb
  • 1009
  • 577 (57%)
• • 출제자
  • 출처
  • 분류
• • JongMan
  • 알고리즘 문제 해결 전략
  • 보기

문제

드래곤 커브(Dragon curve)는 간단한 수학 규칙으로 그릴 수 있는 그림으로, 위 그림같은 형태를 지닙니다. 드래곤 커브는 선분 하나에서 시작해서 간단한 규칙으로 이 선분을 변형해서 만들어지며, 변형이 한 번 이루어져 세대가 변할 때마다 더욱 복잡한 모양으로 진화합니다. 이 도형같이 일부를 확대했을 때 전체와 비슷한 형태로 구성된 도형들을 프랙탈(fractal) 이라고 하지요.

드래곤 커브를 그리는 방법을 드래곤 커브 문자열이라고 부릅시다. 드래곤 커브 문자열은 X, Y, F, +, -로 구성된 문자열인데, 우리는 한 점에서 시작해 다음과 같이 커브를 그리면 됩니다.

• F: 앞으로 한 칸 전진하며 선을 긋습니다.
• +: 왼쪽으로 90도 회전합니다.
• -: 오른쪽으로 90도 회전합니다.
• X, Y: 무시합니다.

0세대 드래곤 커브를 그리는 문자열은 선분 하나인 FX 입니다. 그리고 그 이후의 다음 세대는 이전 세대 문자열의 각 글자를 다음과 같이 치환해서 만들어집니다.

• X => X+YF
• Y => FX-Y

따라서 1, 2세대 드래곤 커브 문자열은 다음과 같습니다.

• 1세대: FX+YF
• 2세대: FX+YF+FX-YF

n세대 드래곤 커브 문자열을 구하고 싶습니다. 이 때 문자열 전체를 구하면 너무 기니, 문자열 중 p번째 글자부터 l글자만을 계산하는 프로그램을 작성하세요.

입력

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

출력

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

예제 입력

4
0 1 2
1 1 5
2 6 5
42 764853475 30 

예제 출력

FX 
FX+YF 
+FX-Y 
FX-YF-FX+YF+FX-YF-FX+YF-FX-YF- 

어떻게 풀까?

해당 문제는 규칙을 이용해서 풀었습니다.

해당 문제는 몇 번 손으로 답을 구해가면 규칙을 찾을 수 있습니다.

우선, 나오는 글자는

+FX, -FX, +YF, -YF가 반복해서 나오는 구조입니다.

또한, 

+FX에서 세대가 늘어나면 +FX+YF

-FX에서 세대가 늘어나면 -FX+YF

+YF에서 세대가 늘어나면 +FX-YF

-YF에서 세대가 늘어남녀 -FX-YF가 됩니다.

이렇게 보면, 0 세대 글자는 +FX로 해도 아무런 문제가 없다는 것을 깨달을 수 있습니다!

(심지어, l이 1부터 시작하기 때문에 인덱스 문제도 쉽게 해결할 수 있습니다. 0번 인덱스가 +로 채워져 있기 때문이죠!)

처음에 입력으로 주어지는 p에서 나누기 3을 하면 몇 번 째 글자인지 알 수 있습니다.

3번 예제같은 경우 p가 6이므로, 2번째 글자를 원한다는 것을 알 수 있습니다!

그리고, p%3을 하면 글자에서 몇 번째 문자를 원하는지 알 수 있습니다.

3번 예제로 다시 설명을 드리겠습니다!

2세대: +FX+YF+FX-YF

2세대의 2 번째 글자는 +YF입니다.

p가 7이면 7%3 = 1 이므로, 2번째 글자의 1번 인덱스글자인 Y부터 출력하면 되고,

p가 8이면 8%3 = 2 이므로, 2번째 글자의 2번 인덱스글자인 F부터 출력하면 됩니다.

그렇다면 해당 세대의 글자는 어떻게 구할 수 있을까요!?

해당 세대의 글자에서 나누기 2를 한 위치에 있는 전 세대의 글자를 이용하면 바로 해당 세대의 글자를 얻을 수 있습니다!

1세대와 2세대를 예로 설명하겠습니다!

• 1세대: +FX+YF
• 2세대: +FX+YF+FX-YF

2세대의 0번글자와 1번글자는 1세대의 0번 글자인 +FX의 글자를 확장한 +FX와 +YF라는 것을 알 수 있습니다!

마찬가지로 2세대의 2번째 글자와 3번째 글자인 +FX와 -YF도 1세대의 +YF를 확장한 결과라는 것을 알 수 있죠!

그런데, p가 10^9 이기 때문에 메모이제이션을 활용하기 힘듭니다!

그래서 메모이제이션을 간략하게 하기위한 전략이 필요하죠.

바로, 메모이제이션에 있는 0번 인덱스에 오는 글자의 위치를 저장하는 방법입니다!!

세대마다 0번 인덱스에 들어와야하는 글자 위치가 다르기 때문에 공간을 배열로 여러개 만들어 두어야 합니다!

(어짜피 처음에 들어있던 시작 위치에서 2씩 나누면 해당 세대의 첫 글자가 오긴 합니다.)

그림을 통해 확인해 보겠습니다!

len[]이 세대마다 시작하는 글자수를 저장한 것이고, memoi[][]가 세대마다의 글자 위치를 저장한 것이라고 하겠습니다!

gen은 세대를 의미합니다!

만약 50세대의 524번째 글자부터 시작하는 글자를 찾기 위해서라면, len[50]에 524를 저장합니다.

그러면 나머지 len값은 len[gen] = len[gen+1] / 2 의 식을 통해서 저장할 수 있습니다!

그러면 이제 memoi[gen][idx] 에는 idx + len[gen] 위치의 글자가 들어있게 됩니다!

l이 최대 50개 이므로, 최악의 경우를 대비해서 18글자가 들어갈 수 있도록 하면 문제가 없습니다!

출력할 때에도 memoi[gen]을 이용하여 결과 문자열을 만들어서 p%3부터 p%3 + l - 1 까지의 글자를 출력해주면 됩니다!

그리고, 만약 찾고자 하는 글자가 짝수라면, 부모 글자에서 2개의 글자를 생성할 수 있기 때문에 다음 글자까지 알아낼 수 있습니다!

이를 이용하면 조금 더 메모이제이션을 빠르게 수행할 수 있을 것입니다!

코드

#pragma once
#include<cstdio>
#include<cstring>
 
char res[55]; // 결과 저장
const char type[4][4] = { "+FX", "-FX", "+YF", "-YF"}; //글자 타입은 4 개가 나온다.
const int conv[4][2] = { {0,2}, {1,2}, {0,3}, {1,3} }; //부모 글자로부터 만들어질 수 있는 글자들
 
int memoi[51][20];
 
int st[51]; // 메모이제이션에서 시작 되는 글자의 위치
 
void getGen(int gen, int p)
{
    int &ret = memoi[gen][p - st[gen]];
    
    if (ret != -1)
    {
        return;
    }
 
    //부모 세대 글자를 알아낸다.
    getGen(gen - 1, p / 2);
 
    //부모 세대로부터 만들어지는 2 개의 글자들
    int *change = (int*)conv[memoi[gen - 1][p / 2 - st[gen-1]]];
 
    //하나밖에 못채움
    if (p % 2)
    {
        ret = change[1];
 
    }
    //두개 다 채울 수 있음
    else
    {
        ret = change[0];
        memoi[gen][p - st[gen] + 1] = change[1];
    }
}
 
int main()
{
    int t;
    scanf("%d\n", &t);
 
    for (int tc = 1; tc <= t; tc++)
    {
        memset(memoi, -1, sizeof(memoi));
 
        memoi[0][0] = 0; // 첫 번째 세대 글자는 +FX
 
        int gen, p, l;
 
        scanf("%d %d %d\n", &gen, &p, &l);
 
        st[gen] = p / 3; //첫번째 글자의 시작 위치
 
        //첫 번째 글자의 위치로 부터 부모 세대들의 시작 글자 위치를 알 수 있다.
        for (int i = gen - 1; i >= 0; i--)
        {
            st[i] =  st[i+1] / 2;
        }
 
        //글자를 찾는다.
        for (int i = 0; i < l / 3 + 2; i++)
        {
            if (memoi[gen][i] == -1) getGen(gen, st[gen] + i);
        }
 
        int len = 0;
 
        //찾은 글자를 바탕으로 결과값을 채운다.
        for (int i = 0; i < l / 3 + 2; i++)
        {
            res[len++] = type[memoi[gen][i]][0];
            res[len++] = type[memoi[gen][i]][1];
            res[len++] = type[memoi[gen][i]][2];
        }
        res[l + p % 3] = 0;
 
        printf("%s\n", res + p % 3);
    }
    return 0;
}

여담

시간복잡도는 어떻게 될까요!?

getGen() 함수는 입력받은 세대 수(n) 만큼 진행되고, 해당 함수를 l / 3 + 2번 반복하기 때문에

O(n * l)이 됩니다.