좋은수열

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	11169	5455	4188	50.144%

문제

숫자 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

7

예제 출력 1

1213121

출처

Olympiad > 한국정보올림피아드 > KOI 1997 > 중등부 1번

• 문제의 오타를 찾은 사람: busyhuman, mwy3055

알고리즘 분류

• 백트래킹

---

1차 시도
BFS로 모든 경우를 다 만들어 놓고 시작하려니 N이 80 이 되는 순간 프로그램이 나락을 간다.

실패코드

#include <iostream>
#include <queue>
#include <cmath> 

using namespace std;

queue<pair<int,int>> myQueue;

int N;

void BFS(int N)
{
	myQueue.push({0, N});

	while (!myQueue.empty())
	{
		int x = myQueue.front().first;
		int n = myQueue.front().second;
		myQueue.pop();

		cout << n << " \n";
		if (n == 0)
		{
			//cout << x << " \n";
			continue;
		}
		for (int i = 1; i <= 3; i++)
		{
			if (i == 1)
			{
				myQueue.push({ x + 1 * pow(10, n - 1), n-1 });
			}
			else if (i == 2)
			{
				myQueue.push({ x + 2 * pow(10, n - 1), n - 1 });
			}
			else if (i == 3)
			{
				myQueue.push({ x + 3 * pow(10, n - 1), n - 1 });
			}
		}
	}

}


int main()
{
	cin >> N;
	BFS(N);
	return 0;
}

계산 중 깊이를 측정해보니 이건 노답 이라는 것을 깨달았다.

DFS로 변경
목표는 가장 낮은 숫자를 찾는 것 => 1부터 시작해서 탐색

#include <iostream>
#include <queue>
#include <cmath> 

using namespace std;

int N;

void DFS(int n, int value)
{
	if (n == 0)
	{
		cout << value << "\n";
		return;
	}

	for (int i = 1; i <= 3; i++)
	{
		if (i == 1)
		{
			DFS(n - 1, value + 1 * pow(10, n - 1));
		}
		else if (i == 2)
		{
			DFS(n - 1, value + 2 * pow(10, n - 1));
		}
		else if (i == 3)
		{
			DFS(n -1, value + 3 * pow(10, n - 1));
		}
	}
}

int main()
{
	cin >> N;
	DFS(N, 0);
	cout << "end";
	return 0;
}

N은 80까지 가능
80 자리…
string 으로 변환….

#include <iostream>
#include <string>

using namespace std;

int N;

void DFS(int n, string value)
{
	if (n == 0)
	{
		cout << value << "\n";
		return;
	}

	
	for (int i = 1; i <= 3; i++)
	{
		if (i == 1)
		{
			DFS(n - 1, value + '1');
		}
		else if (i == 2)
		{
			DFS(n - 1, value + '2');
		}
		else if (i == 3)
		{
			DFS(n - 1, value + '3');
		}
	}
}

int main()
{
	cin >> N;
	DFS(N, "");
	cout << "end";
	return 0;
}

조건에 부합하는 가장 처음 값이 정답

성공 코드(DFS)

#include <iostream>
#include <string>

using namespace std;

int N;
string number;

void DFS(char ch, int cnt)
{
	// 제일 먼저 조건에 부합하는 숫자가 답
	if (cnt - 1 == N) { 
		cout << number; 
		exit(0);
	}
	
	number += ch;
	
	for (int i = 1; i <= cnt/2; i++)
	{
		string a = number.substr(cnt - i, i);
		string b = number.substr(cnt - i * 2, i);

		if (a == b){ 
			// 나쁜 수열이면 지우고 리턴
			number.erase(cnt - 1);
			return;
		}
	}

	for (int i = 1; i <= 3; i++)
	{
		DFS(i + '0', cnt + 1);
	}

	// cnt - 1 자리가 성립하지 않을 경우
	number.erase(cnt - 1);
}

int main()
{
	cin >> N;
	for (int i = 1; i <= 3; i++)
	{
		// '0' 에서 i 만큼 더하면 i
		DFS(i + '0', 1);
	}

	return 0;
}