[백준 2661] 좋은수열 (C++)

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

문제

---

숫자 1, 2, 3으로만 이루어지는 수열이 있다. 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 그 수열을 나쁜 수열이라고 부른다. 그렇지 않은 수열은 좋은 수열이다.

다음은 나쁜 수열의 예이다.

• 33
• 32121323
• 123123213

다음은 좋은 수열의 예이다.

• 2
• 32
• 32123
• 1232123

길이가 N인 좋은 수열들을 N자리의 정수로 보아 그중 가장 작은 수를 나타내는 수열을 구하는 프로그램을 작성하라. 예를 들면, 1213121과 2123212는 모두 좋은 수열이지만 그 중에서 작은 수를 나타내는 수열은 1213121이다.

 

입력

---

입력은 숫자 N하나로 이루어진다. N은 1 이상 80 이하이다.

 

출력

---

첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다.

 

문제 풀이

---

백트래킹 문제.

백트래킹 함수를 만들어서 각 깊이마다 수열[깊이]가 각각 1, 2, 3일 때 일부분이 동일한 수열을 만드는지 확인하면 된다.

깊이가 depth일 때, index 0부터 depth-1까지의 수열은 동일한 수열을 만들지 않으므로, 확인해야 할 부분 수열은 수열[depth]를 포함하며 길이 1부터 (depth+1) / 2까지 확인해주면 된다. 1부터 (depth+1)/2까지 동일한 부분 수열이 없다면 다음 깊이의 탐색을 진행하며, 아니라면 수열[깊이]에서 해당 숫자는 등장할 수 없다.

길이 N짜리 좋은 수열은 여러 개 등장하므로 가장 첫번째 좋은 수열을 찾으면 더 이상 탐색하지 않도록 bool 타입 변수의 플래그를 세워 확인한다. 

 

아래는 코드.

#include <iostream>
using namespace std;
int N;
char* arr;
bool isFound;

void backTracking(int depth)
{
	if (depth == N)
	{
		for (int i = 0; i < N; i++)
		{
			cout << arr[i];
		}
		cout << "\n";
		isFound = true;
	}
	else
	{
		for (int i = 1; i <= 3; i++)
		{
			bool hasSameString = false;
			arr[depth] = i + 48;
			for (int length = 1; length <= ((depth+1) / 2); length++)
			{
				string str1 = "";
				string str2 = "";
				for (int j = 0; j < length; j++)
				{
					str1 += arr[depth-j];
				}
				for (int j = 0; j < length; j++)
				{
					str2 += arr[depth - length - j];
				}
				if (str1 == str2)
				{
					hasSameString = true;
					break;
				}
			}
			if (hasSameString == false && isFound == false)
			{
				backTracking(depth + 1);
			}
		}
	}
}

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

	cin >> N;
	isFound = false;
	arr = new char[N];
	backTracking(0);
	return 0;
}