문제
https://www.acmicpc.net/problem/10597
문제해설
숫자로 이루어진 문자열이 주어진다.
이 문자열은 1~n까지의 숫자로 이루어져 있는데 공백이 지워졌다.
공백이 없어지기 전 숫자들의 나열을 만들어내면 된다.
문제풀이
잘 생각을 해보면
재귀를 이용해야 풀 수 있을것 같다는 생각이 들 것이다.
chk배열을 이용해 숫자가 체크되었는지 확인하고
체크되어있지 않다면 해당숫자를 res벡터에 넣었다.
벡터에 최종 결과값이 저장된다.
주의할 점은 가장 큰 수를 알아야 한다는 것이다.
왜냐하면 모르는 상태에서 돌리게되면
숫자 하나가 빠져서 결과가 만들어질 수 있다.
1
2
3
4
if (arr.length() < 10)
maxx = arr.length();
else
maxx = (arr.length() - 9) / 2 + 9;
이런식으로 가장 큰 수를 구할 수 있다.
그리고 한번 더 깨달았지만
재귀에서는 ++로 들어가면 안된다.
예를들어 dfs(now, idx++);을 사용한다면
dfs가 한번 더 돌고나서 값이 증가가된다.
이를 막기 위해 dfs(now, ++idx);로 쓰거나
dfs(now, idx+=1);로 사용해야 한다.
전체코드
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
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
string arr;
int chk[51];
vector<int>res;
int maxx;
void dfs(int now, int idx) {
if (idx == arr.length()) {
for (int i = 0; i < res.size(); i++)
cout << res[i] << " ";
exit(0);
}
now = arr[idx] - '0';
if (!chk[now]) { //한자리씩 증가하는 경우
chk[now]++;
res.push_back(now);
dfs(now, idx+=1);
res.pop_back();
chk[now] = 0;
idx--; // 이 부분때문에 고생함 재귀가 완전 끝난게 아니라면 이전값으로 돌아가지 않는다
}
if (idx >= arr.length() - 1)
return;
now = (arr[idx] - '0') * 10 + (arr[idx + 1] - '0');
if (!chk[now]) { //두자리씩 증가하는 경우
if (chk[now] || now > maxx) return;
chk[now]++;
res.push_back(now);
dfs(now, idx+=2);
res.pop_back();
chk[now] = 0;
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> arr;
if (arr.length() < 10)
maxx = arr.length();
else
maxx = (arr.length() - 9) / 2 + 9;
dfs(arr[0], 0);
return 0;
}