문제

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

---

풀이

처음에 접근했던 방법은.. 1, 2, 3으로만 이루어진 N자리 정수 중에서 나쁜 수열을 제외하는 방법이다.

그런데 N자리 정수를 모두 구한다 쳐도, 나쁜 수열을 어떻게 판별할 것인가 고민이었다.

임의의 길이의 인접한 두 개의 부분 수열이 동일한지를 어떻게 판별할까..??

단순히 배열을 순회하면서 따지기에는 코드가 너무 복잡해질 거 같았다. 결국 다른 사람 풀이를 참고했는데 너무 신박한 풀이였다. 백트래킹을 이렇게도 활용할 수 있구나!

바로 빈 문자열 "" 부터 시작하여 뒤에 1, 2, 3을 하나씩 붙이면서 모든 경우의 수를 탐색하는 것이다. 그러다가 좋은 수열을 하나라도 발견하면 그게 곧 최솟값이기 때문에, 다른 경우의 수는 구하지 않고 바로 가지치기 한다. 그리고 임의의 길이의 인접한 두 개의 문자열이 동일한, 나쁜 수열을 발견하면 더 이상 깊게 들어가지 않고 다른 경우의 수로 가지치기 한다.

나쁜 수열은 어떻게 판별할까! 이게 가장 핵심인데, 바로 문자열의 일부만 추출하여 서로 비교하는 것이다.

예를 들어 다음과 같은 수열에 대해, substr 함수를 이용하여 (len - i) 인덱스부터 i개, (len - 2*i) 인덱스부터 i개의 문자를 추출하여 서로 같은지 비교하면 된다. (i의 범위는 1부터 len/2)

123|123

추출한 문자열이 같으면, 인접한 부분 수열이 동일한 것이므로 나쁜 수열로 판별하여 다른 경우의 수로 넘어간다.

bool isBadSeq(string str) {
	int len = str.size();
	
	for(int i = 1; i <= len / 2; i++){
		string rear = str.substr(len - i, i); 
		string front = str.substr(len - 2 * i, i); 
		if(rear == front) return true;
	}

	return false; 
}

C++ 코드

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef pair<int, int> pii; 
typedef long long ll;

int N; 
bool isFinish = false; 
string answer = "";

void input(){
	cin >> N; 
}

bool isBadSeq(string str) {
	int len = str.size();
	
	for(int i = 1; i <= len / 2; i++){
		string rear = str.substr(len - i, i); 
		string front = str.substr(len - 2 * i, i); 
		if(rear == front) return true;
	}

	return false; 
}

void dfs(string result, int cnt){
	// 좋은 수열 중에서 최솟값을 구한 경우, 종료 
	if(isFinish) return;

	// 나쁜 수열인 경우, 다른 경우의 수로 넘어감. 
	if(isBadSeq(result)) return;

	// 좋은 수열 발견 (첫번째 경우만 저장하면 된다.)
	if(cnt == N){
		answer = result;
		isFinish = true;
		return;
	}

	// 1, 2, 3으로 이루어진 N자리 정수 만들기 
	dfs(result + '1', cnt + 1);
	dfs(result + '2', cnt + 1);
	dfs(result + '3', cnt + 1);
}

void solution() {
	dfs("", 0);
	cout << answer; 
}

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

	input(); 
	solution(); 

	return 0; 
}