[BOJ] 2661. 좋은 수열 (backtracking)

Gold IV

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

2661번: 좋은수열

숫자 1, 2, 3으로만 이루어지는 수열이 있다.

임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 그 수열을 나쁜 수열이라고 부른다. 그렇지 않은 수열은 좋은 수열이다.

다음은 나쁜 수열의 예이다.

• 33
• 32121323
• 123123213

다음은 좋은 수열의 예이다.

• 2
• 32
• 32123
• 1232123

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

 

input:

• 입력은 숫자 N하나로 이루어진다. N은 1 이상 80 이하이다.

 

output:

• 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다.

 

---

Idea :

• 수열 만들기 문제 → DFS
• 인접한 두 개의 부분 수열이 동일한 것이 없는, 좋은 수열 중 가장 작은 수를 구해야 함
  • 동일한 부분수열이 서로 인접해 있는 경우만 좋은 수열이 아닌 것이므로 two stack을 응용
  • 수열의 뒷부분을 스택으로 옮긴 후 남겨진 수열의 뒷부분(스택 부분수열과 인접한 부분)이 스택에 있는 부분수열과 동일한지 확인

Code :   

#include <iostream>
#include <vector>

using namespace std;

int N;

/* check_same: 좋은 수열인지 확인하는 함수
 *             인접한 두 개의 부분수열 중 동일한 것이 있는지 확인하는 함수
 * parameters - str: 확인하고자 하는 수열
 * return - 좋은 수열이면 true, 아니면 false
 */
bool check_same(string str) {
	vector<char> a;
	vector<char> b;

	for (char ch : str) a.push_back(ch);
	// 뒤에서부터 숫자 하나씩 b로 옮기면서 a의 끝에 b와 동일한 수열이 있는지 확인
	while (a.size() > b.size()) {
		bool isSame = true;
		b.push_back(a.back()); a.pop_back(); 
		auto it_a = a.end()-1;
		for (auto it_b : b) {
			if (*it_a-- != it_b) {
				isSame = false;
				break;
			}
		}
		if (isSame) return true;
	}
	return false;
}

void dfs(int depth, string str) {
	if (depth == N) {
		cout << str << "\n";
		exit(0);
	}

	for (int i=1; i<=3; i++) {
		if (str.back() == i + '0') continue;
		string new_str = str + to_string(i);
		if (!check_same(new_str)) 
			dfs(depth+1, new_str);
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	// freopen("input.txt", "rt", stdin);

	cin >> N;
	dfs(0, "");
}

 

---

Result : 

메모리: 2024 KB,  시간: 0 ms

 

Review :