[ boj : 2661 ] 좋은 수열

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

2661번: 좋은수열

해설 : 일단 백트래킹 문제라는 건 바로 알아채려야 합니다.

다만, 좀 까다로운 부분이 두 부분수열이 반복되서 나타나는걸 어떻게 처리를 해주냐???이게 정말 짜증나는 부분인 것 같아요.

 

이부분은 따로 소스로 적을테니 한번 직접 노트와 펜으로 끄적이면서 익혀보시길 추천드릴게요

 

중요한건, 내가 방금 추가한 숫자가 모두 '나쁜 수열'을 만들 수 있으면, 이전에 만들었던 수도 다시 뜯어 고쳐야 되는 상황이 발생합니다. 

 

따라서 마지막에 반드시 return false 를 적어주시는 걸 까먹지 마세요.

 

#include<bits/stdc++.h>

using namespace std;

int n;
string ans = "";

void solve();
bool dfs(int depth, string num);

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int t = 1;
	while (t--)solve();
	return 0;
}
void solve()
{
	string str = "";
	cin >> n;
	dfs(0, str);
	cout << ans;
}
bool dfs(int depth, string num)
{
	for (int i = 1; i <= num.length() / 2; i++)
	{
		string x = num.substr(num.length() - i, i);
		string y = num.substr(num.length() - i * 2, i);

		if (x == y)return false;
	}
	if (depth == n) {
		ans = num;
		return true;
	}

	for (int i = 1; i <= 3; i++)
	{
		num += (i + '0');
		if (dfs(depth + 1, num) == true)return true;
		num.pop_back();
	}
	return false;
}