백준 2661: 좋은수열

문제 요약

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

길이가 N인 좋은 수열들을 N자리의 정수로 보아 그중 가장 작은 수를 나타내는 수열을 구하는 프로그램을 작성하라. 예를 들면, 1213121과 2123212는 모두 좋은 수열이지만 그 중에서 작은 수를 나타내는 수열은 1213121이다.

문제 분류

• 백트래킹

문제 풀이

0번 인덱스부터 1,2,3을 차례대로 넣어보면서 탐색하면 된다. 1부터 숫자를 삽입했을때 좋은 수열로 판단된다면 계속해서 탐색하고, 아니라면 2, 3으로 차례대로 넣어보면 된다.

어떠한 수열이 좋은수열인지 검사할 때에는 만일 idx번 인덱스에 새로 값이 들어왔을 경우, idx - 1번째까지의 수열은 좋은수열임을 전제한다. 따라서 그 전 수열에 대해서는 판단하지 않아도 되고, idx번째의 수를 포함한 경우만 검사하면 된다. 가장 끝의 인덱스에서부터 간격을 1부터 늘려가면서 검사하면 되는데, j에 가장 끝의 인덱스 i로 초기화하고, 간격을 i라고 하다면, res[j]와 res[j - i]를 해당 간격만큼 비교하는 것이 된다. 이때 두 값이 같은 경우에만 개수를 세준다. 그리고 센 개수가 i와 같을 때, 반복되는 수열을 찾은것이므로 false를 리턴한다. 1212를 예로, 간격을 2인 경우를 보면

인덱스	0	1	2	3
res[]	1	2	1	2

j는 3, 그리고 비교대상(j-2)는 1이 되어 res[3]과 res[1]을 비교하게 된다. 그 둘은 2로 같으므로 cnt는 1이 된다.

다음 j를 1낮추어 2부터 비교하는데, res[2]와 res[0]을 비교하게된다. 그 둘 역시 1로 같으므로 cnt는 2가 된다.

탐색이 종료되었으므로 (j를 더 낮추어 탐색하는 것이 불가) cnt와 간격을 비교하는데 둘이 2로 같으므로 길이가 2인 연속된 수열이 나타나므로 false를 리턴한다.

백트래킹이 그렇지만 이 문제도 상태공간트리로 생각하여 분석하면 더욱 편하다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;

int res[50], n;

bool valid(int idx) {
	if (idx == 0) return true;
	int cnt;
	for (int i = 1; i <= (idx + 1) / 2; i++) {
		cnt = 0;
		for (int j = idx; j > idx - i; j--) {
			if (res[j] == res[j - i]) cnt++;
		}
		if (cnt == i) return false;
	}
	return true;
}

bool dfs(int idx, int val) {
	res[idx] = val;
	if (valid(idx)) {
		if (idx == n - 1) {
			for (int i = 0; i < n; i++)
				printf("%d", res[i]);
			return true;
		}
		if (dfs(idx + 1, 1)) return true;
		else if (dfs(idx + 1, 2)) return true;
		else if (dfs(idx + 1, 3)) return true;
		else return false;
	}
	return false;
}

int main()
{
	cin >> n;
	
	if (dfs(0, 1)) return 0;
	else if (dfs(0, 2)) return 0;
	else dfs(0, 3);
	return 0;
}