[백준/BOJ] 백준 2661번 : 좋은수열

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

2661번: 좋은수열

백트래킹을 통해 수열을 만들어 가며, 만들어지는 수열이 나쁜 수열인지 체크하는 방법으로 문제를 해결했다

 

코드

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

int n;

bool Solve(int index, string& maked)
{
	//해당 문자열이 나쁜 수열인지 확인
	for (int i = 1; i <= maked.size() / 2; i++)
	{
		string check_string = maked.substr(maked.size() - i, i);
		string front_string = maked.substr(maked.size() - i - i, i);

		//같은 문자열일때
		if (front_string == check_string)
			return false;
	}

	//다 만들었을때
	if (index == n)
		return true;


	for (int i = 1; i <= 3; i++)
	{
		maked += to_string(i);

		bool ret = Solve(index + 1, maked);
		if (ret == true)
			return ret;

		maked.pop_back();
	}

	return false;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	string maked = "";

	Solve(0, maked);

	cout << maked;

	return 0;
}