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

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

2661번: 좋은수열

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

 

처음에는 특정한 규칙이 있을 것같았지만, 손으로 몇개 나열해보니 규칙을 찾기가 어려웠다. 

 

따라서, 백트래킹을 통해 작은 수부터 모든 경우의 수를 탐색하면서 좋은수열이면 즉시 종료하였다. 

 

여기서, 중요한건 좋은수열인지 체크하는 방법이다.

그전까지는 좋은 수열이었지만, 특정 숫자를 추가하면서 나쁜 수열이 될수도 있다. 따라서, 문자 하나씩 추가해줄때마다 매번 좋은수열 여부를 체크해준다.

 

체크하는 방법은 마지막 인덱스를 기준으로 길이를 1부터 시작해 (수열의 길이/2)까지 비교하는 것이다. 

 

예를 들어, "12131"에 "2"를 추가한 상황이라고 가정해보자.

그러면 2를 추가함으로써 현재수열에서 만들수 있는 가장 큰 부분수열은 3개가 2번반복되는 것이다.

따라서, 빨간색과 검정색 부분을 비교해서 같은 경우가 한번이라도 있으면 해당 수열은 나쁜수열이 된다.

12131|2     1213|12    121|312

 

아래는 전체코드이다

#include <iostream>
#include <string>
using namespace std;

int N;
string result;
bool finish = false;

void solve(string tmp,int cnt) {
	if (finish ) return;
	int size = tmp.size();
	for (int i = 1; i <= size / 2; i++) {//규칙검사
		if (tmp.substr(size - i, i) == tmp.substr(size - 2 * i, i)) return;
	}
	if (cnt == N) {
		result = tmp;
		finish = true;
	}
	for (int i = 0; i < N; i++) {//백트래킹
		solve(tmp + "1", cnt + 1);
		solve(tmp + "2", cnt + 1);
		solve(tmp + "3", cnt + 1);
	}
}

int main() {
	cin >> N;
	solve("",0);
	cout << result << endl;
}