[종만북]9.동적 계획법 테크닉-드래곤 커브

문제

출처 : https://www.algospot.com/judge/problem/read/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글자를 출력합니다.

풀이(책 참고)

먼저 단순히 특정 문자열을 n세대만큼 진화시키는 메서드를 생각한다. 이는 다음과 같다.

// seed 문자열을 generations세대만큼 진화시켰을 때 결과 문자열
static void curve(String seed, int generations){
    if(generations ==0){
        System.out.print("seed");
        return;
    }
    for(int i=0;i<seed.length();i++){
        if(seed.charAt(i)=='X')
            curve("X+YF",generations-1);
        else if(seed.charAt(i)=='Y')
            curve("FX-Y",generations-1);
        else
            System.out.print(seed.charAt(i));
    }
}

진화 시킬 세대수를 매개변수로 받는데, 문자열을 검사하여 X 또는 Y를 만났을 경우 각 문자가 치환되는 문자에 대해 현재 세대수에서 1만큼 뺀 세대를 진화하도록 재귀호출하여 결과를 찾도록 한다. 여기서 특정 문자열을 진화시킨 후 특정 인덱스의 문자를 찾는다면, 건너뛸 문자의 개수가 skip일 때 재귀함수에서 출력할 문자열의 길이를 비교하여 skip보다 작은 경우 skip에서 해당값을 빼고 진행하고, 큰 경우 skip번째 문자열을 출력하도록 하면 된다.

이 때 0보다 큰 현재 세대에서 문자열을 검사할 때, 해당 문자가 X 또는 Y인 경우 세대를 걸쳐 진화함에 따라 글자의 길이가 증가한다. 이 때, X 또는 Y가 진화가 완료됬을 때 글자수를 안다면 해당 길이를 skip값과 비교하여 건너뛸 수 있다. 점화식에 따라, X 또는 Y는 n세대 진화한 값을 L(n)이라 할 때, L(n) = 2*L(n-1)+2가 성립함을 알 수 있다. 따라서, 이러한 성질을 통해 진화한 세대수에 따른 길이를 배열에 저장하고, 건너뛰는 단계에서 이를 활용하여 효과적으로 skip값을 줄일 수 있다.

static void precalc() {
		length[0] = 1;
		for (int i = 1; i <= 50; i++)
            // 오버 플로 방지
			length[i] = Math.min(MAX, length[i - 1] * 2 + 2);
	}

// cv 문자열을 generations 세대만큼 진화 시킨 후 skip번째 문자
	static char curve(String cv, int generations, int skip) {
		if (generations == 0) {
			if(skip<cv.length())
				return cv.charAt(skip);
			else
				return ' ';
		}
		for (int i = 0; i < cv.length(); i++) {
			char a = cv.charAt(i);
			if (a == 'X' || a == 'Y') {
				if (skip >= length[generations])
					skip -= length[generations];
				else if (a == 'X')
					return curve("X+YF", generations - 1, skip);
				else
					return curve("FX-Y", generations - 1, skip);
			} else if (skip > 0)
				skip--;
			else
				return a;

		}
        //미실행
		return '#';
	}

먼저 length배열에 X또는 Y가 진화한 세대수에 따른 길이를 저장한다. 이후 문자열 cv를 generations세대만큼 진화하였을 때 skip번째 문자를 출력하는 함수 curve를 정의하는데, 기저 사례로 세대수가 0인 경우 skip값과 cv의 길이를 비교하여 skip보다 cv의 길이가 작은 경우 skip번째 문자를 출력하도록 한다.

이후, cv의 각 문자를 순회하여 X 또는 Y와 만났을 때 현재 진화시켜야할 세대수만큼 진화하였을 때 길이가 skip보다 작거나 같은경우는 해당 문자를 건너뛸 수 있음을 의미하므로 skip값에서 해당값을 빼도록 하고, skip보다 큰경우 X또는 Y에 대응하는 문자열을 generations-1 세대만큼 진화하였을 때 skip번째 문자를 출력하도록 한다.

이외의 경우(F,+,-) skip이 0보다 클 때 각 문자를 건너뛰므로 skip값에 1을 빼고, skip이 0일때는 해당 문자를 출력하도록 한다.

Menu

문제

입력

출력

풀이(책 참고)