[동적 계획법] DRAGON 드래곤 커브

1. 완전 탐색

 

이 문제는 다음 과 같은 규칙이 있다

 

gen 0: gen0

gen 1: gen1

gen 2: gen1 + -gen1

gen 3: gen2 + -gen2

gen 4: gen3 + -gen3

.

.

.

gen n: gen n + -gen n

 

여기서 -gen1은 gen1의 가운데 부호를 마이너스를 바꾼 것이다.

 

이를 통해 우리는 완전 탐색 함수를 구현할 수 있다.

 

 

std::string minusDragon(int gen)
{
    if(gen == 1) return "FX-YF";
    return dragon(gen-1) + "-" + minusDragon(gen-1);
}
std::string dragon(int gen)
{
    if(gen == 0) return "FX";
    if(gen == 1) return "FX+YF";
 
    return dragon(gen -1) + "+" + minusDragon(gen-1);
}

 

2. 드래곤의 길이

 

1에서 소개한 규칙에 의해

dragon의 길이를 손쉽게 알 수 있다.

 

 

int count(int gen)
{
    if(gen == 0) return 2;
    int &ret = cnt[gen];
    if(ret != -1) return ret;
 
    ret = (int) std::min<long long>(1000100100ll,(long long)count(gen-1)*2 + 1);
    return ret;
}

오버 플로우 방지를 위해 적당한 값과 비교를 통해 최소값을 넣도록 했다.

 

3. p번째 문자

 

std::string pMinusDragon(int gen, int skip)
{
    if(skip == cnt[gen-1]) return "-";
    if(gen == 1)
    {
        std::string tmp = "FX-YF";
        return tmp.substr(skip,1);
    }
    else if(cnt[gen - 1] < skip)
        return pMinusDragon(gen -1, skip - cnt[gen-1] - 1);
    else
        return pDragon(gen -1, skip);
}
std::string pDragon(int gen, int skip)
{
 
    if (gen == 0)
    {
        std::string tmp = "FX";
        return tmp.substr(skip,1);
    }
    else if(gen == 1)
    {
        std::string tmp = "FX+YF";
        return tmp.substr(skip,1);
    }
    else if(skip == cnt[gen - 1]) 
        return "+";
    else if(cnt[gen - 1] < skip)
        return pMinusDragon(gen -1, skip - cnt[gen-1] - 1);
    else
        return pDragon(gen -1, skip);
}

 

이전 세대 길이와 skip정도를 비교하여

skip이 크면 마이너스 다음세대

같으면 해당하는 부호를 출력하고 중단,

skip이 작으면 다음 세대로 넘어간다.

 

세대를 건너가면서 skip값은 점점 줄어가고

결국 gen 1에 도달하게되어 원하는 문자를 출력한다.

 

이 함수는 하는일이 똑같으므로

if문만 조금 추가하면 함수를 하나로 합칠 수 있다.

 

이 함수를 for문으로 돌리면 원하는 l글자를 얻을 수 있다.

 

4. 시간 복잡도

count하는데 O(gen)

pDragon  O(gen)

pDragon을 l번 호출하므로 O(gen * l)

총O(gen*l)의 시간이 걸린다.

 

pDragon에 l의 정보를 같이 전달하여

l개를 이전세대에 걸친경우에 분할하면

문제를 for문없이 

O(gen)시간복잡도를 가진 함수를

만들 수 있을 것이다.

 

 

DRAGON

 

#include <string>
#include <iostream>
#include <cstring>
#include <algorithm>
 
//gen = n  < p + l
//X = > X + YF
//Y = > FX-Y
//1: FX + YF
//2: FX + YF + FX - YF
 
//n: ... p글자
 
int count(int gen);
std::string minusDragon(int gen);
std::string dragon(int gen);
 
std::string pMinusDragon(int , int);
std::string pDragon(int , int);
int cnt[51];
 
 
 
int main()
{
    int g = 0;
    int p = 0;
    int l = 0;
    memset(cnt, -1, sizeof cnt);
    int testCase = 0;
    std::cin>>testCase;
 
    for(int i = 0; i < testCase; i++)
    {
        std::cin>>g>>p>>l;
        count(g);
        
        std::string tmp = "";
        for(int i = p-1; i < p + l - 1; i++)
            tmp+=pDragon(g, i);
        std::cout<<tmp<<"\n";
    }
}
int count(int gen)
{
    if(gen == 0) return 2;
    int &ret = cnt[gen];
    if(ret != -1) return ret;
 
    ret = (int) std::min<long long>(1000100100ll,(long long)count(gen-1)*2 + 1);
    return ret;
}
std::string minusDragon(int gen)
{
    if(gen == 1) return "FX-YF";
    return dragon(gen-1) + "-" + minusDragon(gen-1);
}
std::string dragon(int gen)
{
    if(gen == 0) return "FX";
    if(gen == 1) return "FX+YF";
 
    return dragon(gen -1) + "+" + minusDragon(gen-1);
}
 
std::string pMinusDragon(int gen, int skip)
{
    if(skip == cnt[gen-1]) return "-";
    if(gen == 1)
    {
        std::string tmp = "FX-YF";
        return tmp.substr(skip,1);
    }
    else if(cnt[gen - 1] < skip)
        return pMinusDragon(gen -1, skip - cnt[gen-1] - 1);
    else
        return pDragon(gen -1, skip);
}
std::string pDragon(int gen, int skip)
{
 
    if (gen == 0)
    {
        std::string tmp = "FX";
        return tmp.substr(skip,1);
    }
    else if(gen == 1)
    {
        std::string tmp = "FX+YF";
        return tmp.substr(skip,1);
    }
    else if(skip == cnt[gen - 1]) 
        return "+";
    else if(cnt[gen - 1] < skip)
        return pMinusDragon(gen -1, skip - cnt[gen-1] - 1);
    else
        return pDragon(gen -1, skip);
}