[백준] 2661번 좋은 수열 (시간초과로 미해결)

https://www.acmicpc.net/problem/2661

2661번: 좋은수열

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

int n;
bool foundAnswer = false;

void select(vector<int> result, int num) {
	if (foundAnswer) return;
	if (num == n) {
		string s = "";
		for (int i = 0; i < n; i++) {
			s += to_string(result[i]);
		}
		for (int i = 0; i < n; i++) { //어디서부터 시작하는지
			for (int j = 1; j < n - i; j++) { //몇개짜리 수열인지
				if (s.substr(i, j) == s.substr(i + j, j)) {
					return;
				}
			}
		}

		foundAnswer = true;
		for (int i = 0; i < n; i++) {
			cout << result[i];
		}
		return;
	}
	for (int i = 1; i <= 3; i++) {
		result[num] = i;
		select(result, num + 1);
	}
}

int main() {
	cin >> n;
	vector<int> result(n);
	select(result, 0);
	return 0;
}

시간초과

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

int n;
bool foundAnswer = false;

void select(string result, int num) {
	if (foundAnswer) return;
	if (num == n) {
		for (int i = 0; i < n; i++) { //어디서부터 시작하는지
			for (int j = 1; j < n - i; j++) { //몇개짜리 수열인지
				if (result.substr(i, j) == result.substr(i + j, j)) {
					return;
				}
			}
		}

		foundAnswer = true;
		cout << result;
		return;
	}
	for (int i = 0; i < 3; i++) {
		result[num] = '1' + i;
		select(result, num + 1);
	}
}

int main() {
	cin >> n;
	string result("");
	for (int i = 0; i < n; i++)
		result.append("1");
	select(result, 0);
	return 0;
}

애초에 string으로 해보았다. 이것도 시간초과

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

int n;
bool foundAnswer = false;

void select(string result, int num) {
	if (foundAnswer) return;
	if (num == n) {
		for (int i = 0; i < n; i++) { //어디서부터 시작하는지
			for (int j = 2; j < n - i; j++) { //몇개짜리 수열인지
				if (result.substr(i, j) == result.substr(i + j, j)) {
					return;
				}
			}
		}

		foundAnswer = true;
		cout << result;
		return;
	}
	for (int i = 0; i < 3; i++) {
		if (num == 0) {
			result[num] = '1' + i;
			select(result, num + 1);
		}
		else {
			if (result[num - 1] == '1' + i) continue;
			result[num] = '1' + i;
			select(result, num + 1);
		}
	}
}

int main() {
	cin >> n;
	string result("");
	for (int i = 0; i < n; i++)
		result.append("1");
	select(result, 0);
	return 0;
}

재귀호출 전에 인접한 것이 같으면 재귀호출을 안 하도록 했는데 이것도 시간초과