[BOJ] 2661번_좋은수열_백트래킹 (C++)

[문제]

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

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

길이가 N인 좋은 수열들을 N자리의 정수로 보아 그 중 가장 작은 수를 나타내는 수열을 구하는 프로그램을 작성하는 문제이다.

예를들어 1213121과 2123212은 모두 길이가 7인 좋은 수열이지만 그 중에서 더 작은 1213121을 출력해야한다.

[사용 알고리즘]

백트래킹

[풀이 핵심]

• N은 1~80인 수인데, 만약 80이라면 수열의 길이가1부터 40일 때까지 전부 비교하면 O(N!)이므로 시간초과가 난다.
• 따라서 브루트포스가 아닌 백트래킹을 이용해서 문제를 풀어야 한다.
• substr함수를 사용하여 길이가 1부터 str.size()/2(총 길이의 절반)까지 인접한 두 부분 수열을 비교한다. 만약 같으면 뒤에 어떤 수를 붙여도 결국 나쁜수열이므로 바로 return하여 백트래킹을 한다.
• N자리 수까지 만들면 나쁜 수열은 백트래킹으로 바로 걸렀으므로 무조건 좋은 수열이다. 그리고 1,2,3순으로(낮은 숫자 순으로) 수를 붙여 가며 진행하므로 처음으로 만들어 진 좋은 수열은 무조건 가장 작은 수열이다.

[코드]

//boj2661번_좋은수열_백트래킹

#include<iostream>
#include<string>

using namespace std;

int N;

void Solve(string str, int count) {
	for (int i = 1; i <= str.size() / 2; i++) {
		string a = str.substr(str.size() - i, i);
		string b = str.substr(str.size() - i * 2, i);

		if (a == b) {
			return;
		}
	}

	if (N == count) {
		cout << str;
		exit(0);
	}

	for (int i = 0; i < N; i++) {
		Solve(str + "1", count + 1);
		Solve(str + "2", count + 1);
		Solve(str + "3", count + 1);
	}
}

int main() {
	cin >> N;
	Solve("", 0);

	return 0;
}