[Algospot] 드래곤 커브 (문제 ID : DRAGON)

문제

드래곤 커브(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글자를 출력합니다.

---

이 문제도 유명한 문제로 백준에서 풀어봤던 기억이 난다. 딱 봐도 재귀를 이용해서 풀어야 할 것 같은 느낌을 준다. 응용이 된 점은 p부터 l까지의 문자열을 출력하는 것인데 p번째의 문자를 구하는 함수를 통해 반복문으로 p+l번째 문자까지 모두 찾아낸다.

K-1번째 답을 찾는 것과는 다르지만 비슷하게 skip 변수를 통해 skip이 0이 되면 그 문자를 반환하는 방식이기 때문에, 각 세대별로 최장 문자열의 길이를 구한다. 문제 조건을 보면 X => X+YF, Y => FX-Y 으로 바뀌는 것을 볼 수 있는데 이는 다시 생각해보면 X를 N세대 진화시킨 길이를 xlen(N)이라 할 때, xlen(N) = xlen(N-1) + ylen(N-1) + 2이고 이는 ylen(N)도 마찬가지이므로 len(N) = 2 * len(N-1) + 2임을 알 수 있다.

이를 활용해서 커브를 구한다. precalc()를 통해 전 세대별 len[i]를 구해준다. 이때도 오버플로에 유의해서 min을 취해준다.

expand 함수를 통해 p번째 문자를 구해야 한다. expand(string dragon, int generation, int skip) 함수는  초기 문자열 "FX"를 받아 genereation 세대 만큼 진화시킨 후 skip 번째 문자를 출력한다. generation == 0이라면 skip번째 dragonCurve를 반환한다.

아니라면 dragonCurve 문자열의 모든 부분을 조사한다. i번째 인덱스의 dragonCurve 문자가 'F', '+', '-'라면 skip을 조정하거나 문자를 반환한다. 'X'나 'Y'라면 이 세대의 최장 길이와 skip을 비교, 조정한다. 아니라면 X나 Y에 맞게 expand 즉 X+YF나 FX-Y로 변경하고 세대를 1 감소한 후 다시 재귀호출한다. skip이 0이 되면 해당하는 문자를 반환한다.

 

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/Algospot/DRAGON.cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int C, N, P, L;
const int MAX = 1000000000 + 1;
const string  EXPAND_X = "X+YF";
const string  EXPAND_Y = "FX-Y";
int len[51]; //X나 Y의 세대별 길이 저장

void precalc()
{
	len[0] = 1; //X나 Y니까 길이는 1
	for (int i = 1; i <= 50; i++) {
		// X를 치환하면 "X+YF"니까 X의 전 세대 길이 + Y의 전 세대 길이  + '+'와'F'의 길이
		len[i] = min(MAX, len[i - 1] * 2 + 2); 
	}
}
char expand(const string& dragonCurve, int generation, int skip)
{
	if (generation == 0) {
		if (skip > dragonCurve.size()) exit(-1);
		return dragonCurve[skip];
	}
	for (int i = 0; i < dragonCurve.size(); i++) {
		if (dragonCurve[i] == 'X' || dragonCurve[i] == 'Y') {
			if (skip >= len[generation]) skip -= len[generation];
			else if (dragonCurve[i] == 'X')
				return expand(EXPAND_X, generation - 1, skip);
			else
				return expand(EXPAND_Y, generation - 1, skip);
		}
		else if (skip > 0) --skip;
		else return dragonCurve[i];
	}
	return '?';
}
int main()
{
	cin >> C;
	precalc();
	while (C--) {
		cin >> N >> P >> L;
		for (int i = 0; i < L; i++) 
			//문자열의 인덱스가 -1이 되기 때문에 p+i-1로 호출
			cout << expand("FX", N, P + i - 1); 
		cout << endl;
	}
}