[백준/C++] 2661번: 좋은수열 (DFS, 백트랙킹)

DFS로 완전탐색을 하되 유망하지 않으면 탐색을 포기하는 기법을 백트랙킹이라고 한다. 이 문제도 역시 백트랙킹으로 푸는 문제이다!

 

1) 출력할 숫자를 어디에 담을 것인가?  -> string에 계속 더해가자.

2) 가지치기 조건은? -> 부분수열이 같은지 체크해서 유효한 수일 때만 dfs! ( 반만 체크하면 된다.)

 

**substr(pos, cnt) pos 위치부터 cnt 갯수만큼의 sub-string을 return

 

 

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

int endFlag = 0;
int N;

bool isValid(string result) {
	int len = result.size();
	int end = len - 1;

	for (int i = 1; i <= len / 2; i++) {
		string a = result.substr(end - i, i);
		string b = result.substr(end, i);
		if (!a.compare(b)) return false;
		--end;
	}
	return true;
}

void dfs(int step, string result) {
	if (endFlag == 1) return; //처음 만난 이후 flag=1이므로 출력 x
	if (!isValid(result)) return; //가지치기 조건
	if (step == N) {
		cout << result << '\n'; //처음 만나면 출력
		endFlag = 1;
		return;
	}
	dfs(step + 1, result + '1');
	dfs(step + 1, result + '2');
	dfs(step + 1, result + '3');
}
int main() {

	cin >> N;
	dfs(0, "");

	return 0;
}