algospot :: DRAGON 드래곤 커브

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

알고리즘 문제 해결 전략 1권 p.306

[알고리즘 STEP. 1]

일단 주어진 세대의 문자열 전체를 출력하는 함수를 작성했다.

드레곤 커브 문자열은 세대가 1 이상일 때, X나 Y가 X+YF와 FX-Y로 치환된다.

그렇다면 문자열 상에서 X나 Y를 만났을 때 세대가 1이상이라면 문자열을 치환하면서, 

그 치환한 문자열에서 다시 세대가 1 이상일 때, X나 Y를 X+YF와 FX-Y로 치환하는, 

즉, 재귀적으로 문자열을 치환하는 함수를 호출하면 된다. 

이 함수가 아래의 void play(int n, string s)이다.

주어진 4개의 테스트케이스 중 첫 세개는 정상작동하지만, 네번째 테스트케이스는 너무 길어서 출력하는데 오래걸린다.

//https://algospot.com/judge/problem/read/DRAGON #include <iostream> #define FOR(i, ed) for(int i = 0 ; i < ed; i++) using namespace std; int tc; // input int n, p, l; // for algorithm void play(int n, string s){ if(n==0){ cout << s; return; } FOR(i, s.length()){ if(s[i] == 'X') play(n-1, "X+YF"); else if(s[i] == 'Y') play(n-1, "FX-Y"); else cout << s[i]; } } int main(){ freopen("input.txt", "r", stdin); cin >> tc; proCalSkips(); while(tc--){ cin >> n >> p >> l; play(n, "FX"); cout << endl; } }

[알고리즘 STEP. 2]

오래걸리는 네번째 테스트케이스는 나중에 처리 하기로 하고, 이제 위의 함수에서 "찾으려고 하는 문자열"만 출력하도록 한다. 

* void play2(int n, string s)

출력하고자 하는 문자가 아닌 나머지는 "_"를 대신 출력하도록 했다.

입력에서 p는 몇 번 째 자리부터 출력하고 싶은지(=건너뛰어야 하는 문자의 수+1), l에는 출력해야 하는 문자의 수를 주어진다.

p를 하나씩 줄여가면서 p가 1에 도달했을 때부터 l개 만큼 출력하면 원하는 문자열을 출력할 수 있다.

* bool printCheck()

현재 문자를 출력할지/말지를 반환하는 함수이다.

아직 출력해야하는 문자에 도달하지 않았다면(p>1) false를 반환한다.

이 때 지금 문자는 건너뛰는 것이므로 p--;를 해준다.

이미 원하는 만큼 다 출력했으면(l<=0) false를 반환한다.

현재 문자가 출력해야하는 문자라면 true를 반환하며,

현재 문자가 출력되므로 출력해야하는 문자의 수를 하나 줄여준다. l--;

//https://algospot.com/judge/problem/read/DRAGON #include <iostream> #define FOR(i, ed) for(int i = 0 ; i < ed; i++) using namespace std; int tc; // input int n, p, l; // for algorithm bool printCheck(){ if(p>1){ p-=1; return false; } if(l<=0) return false; l--; return true; } void play2(int n, string s){ if(n==0){ FOR(i, s.length()){ if(printCheck()) cout << s[i]; else cout << "_"; } return; } FOR(i, s.length()){ if(s[i] == 'X') play2(n-1, "X+YF"); else if(s[i] == 'Y') play2(n-1, "FX-Y"); else if(printCheck()) cout << s[i]; else cout << "_"; } } int main(){ freopen("input.txt", "r", stdin); cin >> tc; proCalSkips(); while(tc--){ cin >> n >> p >> l; play2(n, "FX"); cout << endl; } }

[알고리즘 STEP. 3]

너무 긴 문자열을 일일이 출력하지 않고 원하는 부분만, 시간 내에 출력하기 위해서는 앞에 필요없는 문자열 만큼을 건너뛰어야 한다.

만약 건너뛰어야 하는 문자의 수(=p)가 n세대의 드레곤커브의 길이보다 길다면, 그냥 그만큼은 건너뛰고 그 다음부터 보면 된다.

예를들어, 세번째 예시 인풋(2 6 5)에서

원래대로라면 다음과 같이 모든 세대를 재귀적으로 호출해서 전체 문자열을 찾은다음에 필요한 부분만 출력 하겠지만,

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

1세대 FX+YF 에서 X를 만났을 때, 

어차피 건너뛰어야 할 문자의 수(=6)가 X를 전개하면 생기는 문자열(X+YF)의 길이(=4) 보다 길다.

이 때, 그냥 X를 전개하지 않고 건너뛰고 p-=4를 해준 후, 바로 +YF 부분으로 넘어가는 것이다.

* void proCalSkips()

이 함수는 각 세대의 dragon curve 문자열의 길이를 미리 계산해서 skips배열에 저장한다.

이 때, 각 세대의 dragon curve 문자열의 길이를 만날때 마다 계산하는 것 보다는 미리 계산해서 저장해두는게 효율적이다.

n세대의 문자열의 길이 L(n)은 다음과 같은 점화식을 따른다

L(n) = L(n-1)*2+2;

이걸 n=50까지 계산하면 int의 범위를 넘어가게 된다.

하지만 어차피 p는 최대 1,000,000,000으로 주어졌으므로 이 이상으로 필요할 일이 없다. 따라서 만약 값이 1,000,000,000 + 100 정도를 넘어간다면 그냥 1,000,000,000 + 100 정도로 두어도 상관없다. 

어차피 배열의 값은 p와 크기비교를 하는데 이용을 할 뿐이고, p보다 크기가 작을 때에만 p-특정값을 하므로 그 때만 정확한 값이 필요하다

const int M = 1000000100; int skips[51]; void proCalSkips(){ skips[0] = 1; for(int i = 1; i < 51; i ++){ skips[i] = min(M, skips[i-1]*2+2); } }

이제 이 함수를 이용해서 앞의 불필요한 값을 건너뛰고 필요한 문자열만 출력하는 알고리즘을 작성할 수 있다.

[최종코드]

#include <iostream> #define FOR(i, ed) for(int i = 0 ; i < ed; i++) using namespace std; int tc; // input int n, p, l; // for algorithm const int M = 1000000100; int skips[51]; void proCalSkips(){ skips[0] = 1; for(int i = 1; i < 51; i ++){ skips[i] = min(M, skips[i-1]*2+2); } } bool printCheck(){ if(p>1){ p-=1; return false; } if(l<=0) return false; l--; return true; } void play3(int n, string s){ if(l<=0) return; if(n==0){ FOR(i, s.length()){ if(printCheck()) cout << s[i]; } return; } FOR(i, s.length()){ if(s[i] == 'X'){ if(skips[n] < p) { p -= skips[n]; } else play3(n-1, "X+YF"); } else if(s[i] == 'Y') { if(skips[n] < p) { p -= skips[n]; } else play3(n - 1, "FX-Y"); } else { if(printCheck()) cout << s[i]; } } } int main(){ freopen("input.txt", "r", stdin); cin >> tc; proCalSkips(); while(tc--){ cin >> n >> p >> l; play3(n, "FX"); cout << endl; } }

[내가 실수한 부분]

*void play3(int n, string s) 에서 이미 필요한 문자열을 다 출력 했다면 더 이상 문자열을 만들 필요 없이 종료하면 된다.

if(l<=0) return;

이 종료조건을 넣지 않아서 계속 시간초과가 떴다.

*void proCalSkips() 에서 int값을 넘어갈 때 다른 값을 대신 저장하는 부분도 생소했다.