[BOJ/C++] 2661 좋은수열

문제

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

풀이

백트래킹 문제이다.
재귀호출하며 조건을 충족하지 않는 경우에는 return해가며 가지치기 해야한다.

• 빈 문자열에서 1, 2, 3 붙여가면서 재귀호출
• 문자열을 만든 후, 동일한 부분 수열이 있는지 검사해야 한다.
  • 문자열의 절반 길이만큼 반복문 수행
  • 부분 문자열 추출해서 비교
  • str = 1231, i가 1인 경우, 젤 뒤에 1 vs 3
  • i가 2인 경우, 31 vs 12
• 문제가 요구하는 길이에 도달하면 프로그램 종료

⚠️ 가장 작은 수를 출력해야하므로 flag을 사용해서 처음에 발견한 수열을 출력하고, 그 뒤로는 탐색하지 않아야한다.

코드

#include <iostream>
#include <string>

using namespace std;

int N;
string ans;
bool found;

void dfs(string str, int depth) {
	if (found)	return;

	//규칙검사
	for (int i = 1; i <= str.length() / 2; i++) {
		if (str.substr(str.length() - i, i) == str.substr(str.length() - 2 * i, i))
			return;
	}

	if (depth == N) {
		ans = str;
		found = true;
		return;
	}
	
	dfs(str + "1", depth + 1);
	dfs(str + "2", depth + 1);
	dfs(str + "3", depth + 1);
}

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

	cin >> N;

	dfs("", 0);

	cout << ans;

	return 0;
}