백준 2661 좋은 수열

백준 2661 좋은 수열 문제는 숫자 1,2,3을 이용하여 수열을 만드는 대신 인접한 수열이 동일한 패턴을 가지면 나쁜 수열에 해당되어 이 나쁜 수열이 아니면서 가장 작은 값을 가지는 수열을 찾아내는 문제이다.

예를 들면 12131212라는 수열을 보면 앞의 7자리 1213121까지는 문제가 없는 수열이지만 뒤에 2라는 숫자가 오게되므로 12/12라는 동일한 패턴이 인접해서 발생하므로 나쁜수열이다. 12/12 사이에 3이라는 숫자가 오는 방법으로 121312312 가 되게되면 121/ 312/ 312로 다시 반복되게 되므로 맨뒤의 2를 3으로 바꾸어 주어야 가장 최소의 수열을 만족한다.

이 수열을 만들어내는 가장 쉬운 방법은 dfs를 통해 1,2,3의 숫자를 차례대로 넣어준 뒤(작은 숫자를 만족하기 위해) 이 넣은 숫자가 좋은 수열을 만족하는지 체크하는 것이다. check 함수에는 먼저 넣은 숫자가 전의 숫자와 같을 경우는 바로 빠져나오도록 false를 리턴해 주게 된다. ex) 11,22,33과 같이 똑같은 숫자가 나오면 나쁜 수열이므로

좋은 수열을 체크하는 과정은 위의 그림에서 12131213이라는 수열을 예제로 설명하겠다. 크기가 1인 수열에 대해서는 수를 넣을때 바로 전의 숫자와 같은지로 벌써 판별했기 때문에 크기가 2일때 부터 시작한다. 숫자는 쌓여지면서 좋은수열을 계속 판단하고 숫자를 넣어가기 때문에 숫자가 붙는 오른쪽을 기준으로 인접한 수열이 같은패턴이 있는지 검사한다.

크기가 2인 패턴의 경우를 확인하기 위해 12/13의 인접한 숫자들을 판별한다. for문을 통해 숫자를 비교하면서 두 패턴이 모두 같은 수로 이루어져 있지 않으니 크기 3으로 넘어간다.

크기가 3인 패턴의 경우도 마찬가지로 크기가 3인 오른쪽의 인접한 131/213의 숫자를 판별한다. 여기도 마찬가지로 두 패턴이 같은 수로 이루여져 있지 않으니 크기 4로 넘어간다.

크기 4에서는 모두 비교해보니 1213/ 1213으로 같은 패턴을 보이므로 좋은 수열이 아님을 알 수 있으므로 false를 리턴하고 후보에서 제외한다.

좋은 수열은 현재까지 만들어온 수열 크기의 1/2까지 하면된다. 크기 5이상부터는 같은 길이가 동등한 패턴이 존재 할 수 없으므로 할필요가 없다.

#pragma warning(disable:4996)
#include<iostream>
#include<string.h>
#include<vector>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;

int n;
int arr[81];
bool found = false;

bool check(int depth)
{
	if (arr[depth] == arr[depth - 1]) // 붙어있으면 안됨
		return false;
	if (depth == 0 || depth == 1 || depth == 2)
		return true;
	
	int max_size = (depth + 1) / 2;

	for (int i = 2; i <= max_size; i++)
	{
		bool ok = false;
		for (int j = 0; j < i; j++)
		{
			if (arr[depth - j] != arr[depth - j - i])
			{
				ok = true;
				break;
			}
		}
		if (!ok)
			return false;
	}

	return true;
}


void dfs(int depth)
{
	if (depth == n)
	{
		found = true;
		return;
	}
	for (int i = 1; i < 4; i++)
	{
		arr[depth] = i;

		if (check(depth))
		{
			dfs(depth + 1);
			if (found)
				break;
		}
	}
}

int main()
{
	//freopen("input.txt", "r", stdin);
	scanf("%d", &n);

	dfs(0);

	for (int i = 0; i < n; i++)
	{
		printf("%d", arr[i]);
	}
	printf("\n");
}