[Week 6] DRAGON self review - yujungee

[yujungee]

DRAGON self review

• 파일명: DRAGON/yujungee.cpp
• 수행시간: 0ms

1. 문제 해결 과정

마지막 예시의 값이 계속 다르게 나와 len[i]를 구해줄 때 오버플로의 가능성을 생각해서 min을 해주었더니 해결되었습니다.

2. 아이디어

X의 N세대 길이가 X(N)이라면 X(N) = X(N-1) + Y(N-1) + 2이고 Y(N)도 똑같으므로, L(N) = 2 * L(N-1) + 2임을 도출할 수 있습니다.

3. 코드 설명

상수 선언

const int MAX = 1000000001;
const string X = "X+YF";
const string Y = "FX-Y";
int len[51]; // 세대마다 길이 저장

draw() 함수는 초기 문자열인 FX를 받아 매개변수 genereation 만큼 치환시킨 후 skip 번째 문자를 출력합니다.
generation이 0이라면 skip번째 dragon을 반환합니다.

char draw(const string& dragon, int generation, int skip)
{
    if (generation == 0) {
        if (skip > dragon.size()) return 0;
        return dragon[skip];
    }

generation이 0이 아닐 때,
i번째 인덱스의 dragon 문자가 X나 Y일 때, skip이 len보다 크면 세대를 1 감소시키고 다시 재귀호출합니다.

    for (int i = 0; i < dragon.size(); i++) {
        if (dragon[i] == 'X' || dragon[i] == 'Y') {
            if (skip >= len[generation]) skip -= len[generation];
            else if (dragon[i] == 'X')
                return draw(X, generation - 1, skip);
            else
                return draw(Y, generation - 1, skip);
        }

i번째 인덱스의 dragon 문자가 X나 Y가 아닐 때 (F, +, -)라면 skip을 조정하거나 문자를 반환합니다.

        else if (skip > 0) --skip;
        else return dragon[i];   
    }
    return 0;
}

main함수

int main()
{
    
    len[0] = 1; // 0세대 일 때는 길이 = 1
    for (int i = 1; i <= 50; i++) {
        len[i] = min(MAX, len[i - 1] * 2 + 2);
    }
    
    cin >> tc;
    while (tc--) {
        cin >> n >> p >> l;
        for (int i = 0; i < l; i++)
            cout << draw("FX", n, p + i - 1);    
        cout << endl;
    }
}