알고리즘 문제해결 전략(문제 ID:DRAGON)

OvO·2020년 7월 19일
0

문제해결전략

목록 보기
3/16

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

예제 입력
4
0 1 2
1 1 5
2 6 5
42 764853475 30

예제 출력
FX
FX+YF
+FX-Y
FX-YF-FX+YF+FX-YF-FX+YF-FX-YF-

🤔첫 생각

이 문제는 동적 계획법 파트인 9장에 있는 문제이기 때문에 동적 계획법의 방식으로 접근하려고 시도했다. 하지만 DP로의 접근을 실패하고 분할로의 접근을 성공하였다. 현재 우리가 구하는 n세데는 FX로 부터 시작되는 n세대이다. 이와 마찬가지로 YF로 부터 시작되는 n세대를 구해보면 다음과 같은 식이 성립한다.

FX[n] = FX[n - 1] + "+" + YF[n - 1]
YF[n] = FX[n - 1] + "-" + YF[n - 1]

그래서 n세대에서의 특정 구간 문자열을 FX[0]세대 문자열과 FY[0]세대 문자열을 통해서 구할 수 있다. 현재 세대(n)에서 이전 세대(n-1)로 역행할 때 현재 세대에서의 특정구간 문자열이 중간보다 왼쪽에 있는지, 중간에 걸쳐있는지, 중간 보다 오른쪽에 있는지에 따라 p와 l을 변경해줘야만 한다.

😯부족했던 부분

DP로 문제를 해결하려고 오랫동안 잡고있다가 마지못해서 분할로 코드를 작성했다. 결국에는 DP로는 해결을 못한 셈이다.

😀코드

#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<math.h>

using namespace std;

string cache1[1];
string cache2[1];

string ans(int generation, int pos, int len, int flag) {
	if (len < 0)
		return "";
	if (generation == 0) {
		string tmp;
		for (int i = pos; i < pos + len; i++) {
			if (flag == 0)
				tmp += cache1[generation][i];
			else
				tmp += cache2[generation][i];
		}

		return tmp;
	}
	int sizeGd = generation >= 30 ? 2000000200 : 3 * pow(2, generation) - 1;
	int mid = sizeGd / 2;

	if (pos + len - 1< mid)
		return ans(generation - 1, pos, len, 0);
	else if (pos > mid)
		return ans(generation - 1, pos - mid - 1, len, 1);
	else {
		string ret = ans(generation - 1, pos, mid - pos, 0);
		string sign = flag == 0 ? "+" : "-";
		return ret + sign + ans(generation - 1, 0, pos + len - 1 - mid, 1);
	}
}

int main(void) {
	int C, n, p ,l;

	cache1[0] = "FX";
	cache2[0] = "YF";

	cin >> C;
	for (int i = 0; i < C; i++) {
		cin >> n >> p >> l;

		cout << ans(n, p - 1, l, 0);
		cout << endl;
	}
	return 0;
}

👏후기

책에서는 k번째 단어를 찾는 식으로 k가 p, p + 1, ... , P + l - 1이 되면서 k - 1개를 스킵하면서 답을 찾는다(스킵을 위해 n번째 세대의 문자열 길이를 저장해야 됨). 그리고 드래곤 커브 문자열을 0세대부터 n세대까지 오름차순으로 확장해 나간다.
처음 동적 계획법으로 문제를 풀려고 했을 때 0부터 29세대 까지 문자열을 구하려고 했었다. 하지만 이 방식은 메모리의 한계로 인해서 실패하였다. 이런 방식에서 문자하나씩 스킵을 사용했다면 책에 있는 풀이가 되지 않았을까 싶다. 이런 생각을 못 했던 까닭은 문제를 풀 때 너무 문자열 자체에만 치중한 나머지 문자열의 길이에는 큰 중점을 두지 않아서 그런게 아닐까 싶다.

profile
이유재입니다.

0개의 댓글