좋은수열

 

백트래킹 문제로, 어려운 문제라기보단 귀찮은 문제가아닐까 싶었고, 확신이 쉽게들지않을문제.

첫번째, 일단 재귀를통해 수열을 만드는것은 string을 통해 쉽게 가능함

두번째, 바로앞에 중복되는 값을 수열로만드는건 굉장히 쉬움

세번째, 세번째부터 문제인데, 앞서 사용되있던 문자들과 중복체크하는것 이 굉장히 귀찮다.

하나하나 다해보기엔 시간복잡도가 터져버릴것같은문제,

전략을 세워보면, 딱 반크기만큼만 잘라서 보면된다

전체적으로 다검사해봐야하는것은 맞지만, 이어붙여나가는과정에서 이미 이어붙였던 것까지 한번에 검사할필요는 없다는얘기다.

 

문제를 풀어서 코드로 작성해보면다음과같다.

 

#include<cstdio>	
#include<iostream>
#include<string>
#include<vector>

using namespace std;

vector<string> a[80];
char temping[] = { '1','2','3'};
bool check(string str) {
	string x;
	int len = str.length();
	int start = len - 1;
	for (int i = 1; i <= len / 2; i++) {
		if (str.substr(len - i, i) == str.substr(len -i*2 , i)) {
			return false;
		}
		start -= 1;
	}
	return true;
}
bool ending = false;
void go(int n, string str) {
	if (ending == true) {
		return;
	}
	if (str.length() == n) {
		cout << str << "\n";
		ending = true;
	}
	else {
		for (int i = 0; i < 3; i++) {
			string temp = str;
			if (str.length() >0 && str[str.length()-1] != temping[i]){
				temp += to_string(i+1);
				if (check(temp)) {
					go(n, temp);
				}
			}
			
		}
	}
}


int main() {
	int n;
	cin >> n;
	go(n,"1");
	//go(n, "2");
	//go(n, "3");
	//string al = "hello";
	//for (int i = 0; i < a[n].size(); i++) {
		//cout << a[n][0] << "\n";
	
	return 0;

}

 

아그리고 한가지 처음에, 벡터에다가 문자열을 넣고 출력해보면서 느꼈던것은 늘 제일 작은 숫자가 재귀의 순서에의해 제일 첫번째단에 들어간다는것이다. 그래서 따로 저장한뒤출력할필요가없고, 값이 만들어지는 그대로 출력하고 

재귀를 끄면된다.