문제 출처

1. 문제설명

• 1,2,3으로만 이뤄진 수열이 있다.
• 임의의 길이에 인접한 두 개의 부분 수열이 동일하면, 나쁜 수열이라고 부른다.
• N이 주어졌을 때 N자리의 좋은 수열 중에서 가장 작은 수를 나타내는 수열만 출력한다.

2. 알고리즘 설계

• 가장 작은 수열을 구하는 것이므로, 1-2-3 순서로 조합을 생성한다.
• 인접한 길이의 수열이 동일하면, 해당 조합은 실패한 것으로 간주한다.

3. 로직

• 인접한 길이의 수열 검사
  • 가장 마지막 원소의 인접 수열부터 크기를 1씩 늘려가며 같은지 검사한다.
  • 예시(볼드체 - 검사 대상)
    • 1 2 1 3 1 2 // Input

    • 1 2 1 3 **1

      2**

    • 1 2 1 3 **

      ** 1 2

    • 1 2 1 **

      ** 3 1 2 // True

• 가장 작은 수열은 처음으로 찾은 수열이다.
  • 최초로 찾으면 바로 DFS를 종료한다.

4. 전체 코드

#include<bits/stdc++.h>
using namespace std;

int n;
string res;
bool flag = false;

void dfs(string s, int cnt) {
	if (flag) return;

	int sz = s.size();
	for (int i = 1; i <= sz / 2; i++)
		if (s.substr(sz - i, i) == s.substr(sz - i * 2, i))
			return;

	if (cnt == n) {
		res = s;
		flag = true;
	}

	for (int i = 0; i < n; i++) {
		dfs(s + "1", cnt + 1);
		dfs(s + "2", cnt + 1);
		dfs(s + "3", cnt + 1);
	}
}

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

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

	cout << res;
	return 0;
}