💡 백트래킹
Memory 1228KB Time 8ms Code Length 763B
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<stdio.h>
#include<string>
#include<vector>
using namespace std;
string numstring;
int nsize;
int N;
int visited[51];
vector<int> vec;
void dfs(int index) {
if (index == nsize)
{
if (vec.size() >= N) {
for (int i = 0; i < N; i++) {
printf("%d ", vec[i]);
}
exit(0);
}
return;
}
for (int i = 1; i <= 2; i++) {
string tmp = numstring.substr(index, i);
int tmp_int = stoi(tmp);
if (visited[tmp_int])continue;
if (tmp_int > N) continue;
vec.push_back(tmp_int);
visited[tmp_int] = 1;
dfs(index + i);
visited[tmp_int] = 0;
vec.pop_back();
}
}
int main()
{
char c[100];
scanf("%s",c);
numstring = c;
nsize = numstring.size();
if (nsize <= 9) N = nsize;
else {
N = (nsize - 9) / 2 + 9;
}
dfs(0);
return 0;
}
이 코드는 입력된 문자열을 숫자로 변환하여 가능한 조합을 탐색하는 깊이 우선 탐색(DFS) 알고리즘을 사용한다.
주어진 문자열을 숫자로 변환하고, 변환된 숫자를 이용하여 가능한 조합을 만들어낸다. 만들어진 조합이 주어진 조건을 만족하면 출력하고 프로그램을 종료한다.
주요 함수는 dfs() 함수로, 재귀적으로 모든 가능한 조합을 탐색하며, vec 벡터에 숫자를 추가하고 제거하면서 탐색을 진행한다. 이미 방문한 숫자는 visited 배열을 통해 체크하여 중복 방문을 방지한다.
main() 함수에서는 입력을 받고, 입력된 문자열의 길이에 따라 출력할 숫자의 개수를 결정한다. 그 후 dfs() 함수를 호출하여 가능한 조합을 찾는다.
