💡 백트래킹
Memory 2024KB Time 0ms Code Length 608B
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<iostream>
#include<string>
using namespace std;
int N;
int cnt = 0;
bool isBad(string c) {
int size = c.size();
// i 는 갯수
for (int i = 1; i <= size / 2; i++) {
string first = c.substr(size - (i * 2), i);
string second = c.substr(size - i, i);
if (first == second) return true;
}
return false;
}
void dfs(string tmp, int step) {
if (step == N) {
cout << tmp << endl;
exit(0);
return;
}
if(!isBad(tmp+"1")) dfs(tmp + "1", step + 1);
if(!isBad(tmp+"2")) dfs(tmp + "2", step + 1);
if(!isBad(tmp+"3")) dfs(tmp + "3", step + 1);
}
int main() {
scanf("%d", &N);
dfs("", 0);
}
이 코드는 재귀적으로 문자열을 생성하는 함수를 사용하여 길이가 N인 문자열을 생성하는 프로그램이다. isBad 함수는 생성된 문자열이 특정 조건을 만족하는지 확인하고, dfs 함수는 가능한 다음 문자열을 생성하고 출력하는 역할을 한다. main 함수에서는 입력값을 받고 dfs 함수를 호출하여 실행한다.
