Baekjoon/10597.cpp at master · jaejunha/Baekjoon · GitHub

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <iostream>
#include <cstring>
using namespace std;

int n, l, k, v[1000];
char a[200];
bool b[100], e;

void dfs(int x, int y) {
	if (x == n) {
		if (y != l)
			return;
		for (int i = 1; i <= l; i++) {
			if (!b[i])
				return;
		}

		for (int i = 0; i < l; i++)
			printf("%d ", v[i]);
		e = true;
	}
	else if (x + 1 <= n) {
		if (e || a[x] == '0')
			return;
		int i = a[x] - '0', j;
		if (l >= 10) {
			if (i <= k) {
				j = a[x + 1] - '0';
				if (x + 2 <= n) {
					v[y] = i * 10 + j;
					if (!b[v[y]]) {
						b[v[y]] = true;
						dfs(x + 2, y + 1);
						b[v[y]] = false;
						if (e)
							return;
					}
				}
				v[y] = i;
				if (!b[v[y]]) {
					b[v[y]] = true;
					dfs(x + 1, y + 1);
					b[v[y]] = false;
					if (e)
						return;
				}
			}
			else {
				v[y] = i;
				if (!b[v[y]]) {
					b[v[y]] = true;
					dfs(x + 1, y + 1);
					b[v[y]] = false;
					if (e)
						return;
				}
			}
		}
		else {
			v[y] = i;
			if (!b[v[y]]) {
				b[v[y]] = true;
				dfs(x + 1, y + 1);
				b[v[y]] = false;
				if (e)
					return;
			}
		}
	}
}

int main() {
	scanf("%s", a);
	n = strlen(a);
	if (n <= 9) {
		for (char c : a)
			printf("%c ", c);
	}
	else {
		l = 9 + (n - 9) / 2;
		k = l / 10;
		int i = v[0] = a[0] - '0';
		if (l >= 10) {
			if (v[0] <= k) {
				if (2 <= n) {
					v[0] = v[0] * 10 + (a[1] - '0');
					if (!b[v[0]]) {
						b[v[0]] = true;
						dfs(2, 1);
						b[v[0]] = false;
						v[0] = i;
					}
				}
				if (!b[v[0]]) {
					b[v[0]] = true;
					dfs(1, 1);
					b[v[0]] = false;
				}
			}
			else {
				if (!b[v[0]]) {
					b[v[0]] = true;
					dfs(1, 1);
					b[v[0]] = false;
				}
			}
		}
		else {
			if (!b[v[0]]) {
				b[v[0]] = true;
				dfs(1, 1);
				b[v[0]] = false;
			}
		}
	}
	return 0;
}