[BOJ] 2661 - 좋은 수열

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

---

[알고리즘풀이]

기본 아이디어는 길이 N이 될 때까지, 백트레킹을 이용해 한 자리씩 수열을 늘려간다.

이때, 좋은 수열 중 가장 작은 수를 만들어야 하므로 1부터 차례대로 수열에 추가해본다.

 

-수열에 숫자 추가.

좋은 수열이 되려면 수열[i] 와 수열[i+1]은 달라야 하므로 새롭게 추가되는 수는 수열의 마지막 부분과 달라야 한다.

	for (int i = 1; i <= 3; i++) {
		if (N[N.size() - 1] == i)
			continue;
		N.push_back(i);
		if (check(N))
			bt(n, N);
		N.pop_back();
	}

따라서 1 부터 3 을 넣어볼 건데, 수열 N의 마지막 자리인 N[N.size() - 1] 과 같은 수는 넣어볼 필요가 없다.

 

-수열이 좋은 수열인지, 나쁜 수열이 Check.

수열 N이 좋은 수열인지, 나쁜 수열인지 check 해야 한다.

check는 2개씩 (N.size() / 2) 개까지 check를 해봐야 한다.

bool check(vector<int> N) {
	int k = N.size() / 2;
	for (int i = 2; i <= k; i++) {
		for (int j = 0; j < N.size() - 2 * i + 1; j++) {
			bool flag = true;
			for (int l = 0; l < i; l++){
				if (N[j + l] != N[j + i + l]) {
					flag = false;
					break;
				}
			}
			if (flag)
				return false;
		}
	}
	return true;
}

인덱싱이 조금 까다로워서 주의해야 한다.

 

-최종코드

#include<iostream>
#include<vector>

using namespace std;

bool check(vector<int> N) {
	int k = N.size() / 2;
	for (int i = 2; i <= k; i++) {
		for (int j = 0; j < N.size() - 2 * i + 1; j++) {
			bool flag = true;
			for (int l = 0; l < i; l++){
				if (N[j + l] != N[j + i + l]) {
					flag = false;
					break;
				}
			}
			if (flag)
				return false;
		}
	}
	return true;
}
void bt(int n, vector<int> N) {
	if (N.size() == n) {
		for (int i = 0; i < n; i++)
			cout << N[i];
		exit(0);
	}

	for (int i = 1; i <= 3; i++) {
		if (N[N.size() - 1] == i)
			continue;
		N.push_back(i);
		if (check(N))
			bt(n, N);
		N.pop_back();
	}
}

int main(void){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int n;
	cin >> n;
	vector<int> N;
	N.push_back(1);
	bt(n, N);
}

---