알고스팟 드래곤 커브(ID: DRAGON)(해결못함.. ) - 알고리즘 문제해결 전략 9.9

1. 문제 

algospot.com/judge/problem/read/DRAGON

 

2. 필요한 개념

   - 동적계획법

    : 동적 계획법이란 앞의 사건이 뒤의사건에 영향을 미쳐 앞의 것을 저장해놓고 뒤에 사건을 계산할 때 꺼내 쓰는 것이다 . 

이 문제에서는 앞의 X 가 뒤의 X+YF 가 되고 앞의 Y 가 뒤의 FX -Y 가 된다. 따라서 앞의 사건이 규칙적으로 이루어지며 뒤의 사건에 영향을 주기때문에 다이나믹 프로그래밍으로 풀어야 된다. 

 

3. 내 전략

우선 처음에는 쉽게 생각했다ㅎㅎ /... P가 1,000,000,000개까지 인것을 보기 전까지...

그냥 단순하게 규칙을 보니 FX와 YF 만 달라지고 중간에 +- 만 계속 달라지길래 +-를 STRING에 저장하는 전략을 사용하였다. 

두번째로 앞의 사건이 그대로 뒤에 반복되고 나머지 반틈이 달라진다는 규칙을 봐서 뒤에 달라지는 부분만 저장을 하려했다. 

예를 들어 앞에 XXYY면 뒤의 사건은 XXYY XYXY 이런식으로 반복이 되어 XYXY만 저장을 하려했다.

근데/......... 오버플로우는 CHAR 배열에서 더욱 가혹했다.. 아무리 배열을 만들어도 너무 큰 범위라고 해도 캐쉬 배열이 만들어지지 않았다ㅠㅠ ,,, 

 

그래서 세번째로 점화식을 사용해 보았다.  

 

요런 생각이었는데 정리를 하면 모든 수열의 글자수는 앞의 글자수의 두배+1만큼 길어진다. 

예를 들어 FX -> FX+YF (글자 수 2 -> 글자 수 5)

FX + YF -> FX + YF + FX - YF (글자수 5 -> 11)

즉 an+1  = 2* an +1이라는 점화식이 나오고 이걸 풀면

an의 글자수는 2^(n+1) -1이라는 식이 나온다. 

근데 이걸 계산하고 보니 오버플로가 얼마나 빨리오는지 계산이 되었을 뿐 별 소용은 없었다.. 

그래서 일단 여기까지 풀고 스트링 캐시 배열을 하는 것을 포기하려고 코드를 갈아 엎고 있다..

 

성공을 하면 다시 올리겠다ㅠㅠ 성공했으면 좋겠네.. 

 

 

4. 코드  (실패한 코드!!!)

 

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int cache[51];
int n, p, l;

void nextString(int index) {

	int size = cache[index - 1];
	int half = size / 2;
	for (int i = 0; i < size; i++) {
		cache[index][i] = cache[index - 1][i];
	}

	int newIndex = size;
	for (int i = half + 1; i < size; i++) {
		if (cache[index - 1][i] == 'X') {
			cache[index][newIndex] = 'X'; newIndex++;
			cache[index][newIndex] = '+'; newIndex++;
			cache[index][newIndex] = 'Y'; newIndex++;
			cache[index][newIndex] = 'F'; newIndex++;
		}
		else if (cache[index - 1][i] == 'Y') {
			cache[index][newIndex] = 'F'; newIndex++;
			cache[index][newIndex] = 'X'; newIndex++;
			cache[index][newIndex] = '-'; newIndex++;
			cache[index][newIndex] = 'Y'; newIndex++;
		}
		else {
			cache[index][newIndex] = cache[index - 1][i]; newIndex++;
		}
	}
}

int main() {
	cin >> n >> p >> l;
	cache[0] = "FX";

	for (int i = 1; i < n; i++) {
		nextString(i);
	}

	for (int i = p; i < p + l; i++) {
		cout << cache[n][i];
	}
	return 0;
}

 

5. 결과화면 은 없다.. 끄읕 성공하면 올려야지..