알고리즘
- DP 사용
- 앞에서부터 백트래킹처럼 조건이 맞을때 전진
- 만약 끝까지 갔으면 gotAns = true 설정하여, true이면 바로 종료.
- 만약 끝까지 안갔으면, save에 저장
- 이때 save[현재-2 문자][현재-1문자][남은 A][남은 B][남은 C] 로 함
- 현재 상태를 결정하는 건, 전전문자, 전 문자, 남은 A의 개수, 남은 B의 개수, 남은 C의 개수로 결정되므로.
- 사용한 A,B,C 의 개수가 같다면, 현재-2 이전의 문자 배열은 상관없기 때문이다.
- DP 함수 시작부분에 현재 상태의 save가 true이면 현재 dp 종료
코드
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
#include <bits/stdc++.h>
using namespace std;
string input;
int ABC[3], save[3][3][51][51][51];
char result[100];
bool gotAns = false;
void dp(int n);
void goNext(char cur, int n);
int main() {
cin >> input;
for (int i = 0; i < input.size(); i++) {
if (input[i] == 'A') {
ABC[0]++;
}
else if (input[i] == 'B')
ABC[1]++;
else
ABC[2]++;
}
dp(0);
if (gotAns) {
for (int i = 0; i < input.size(); i++)
cout << result[i];
}
else
cout << -1;
}
void goNext(char cur, int n) {
ABC[cur - 'A']--;
result[n] = cur;
dp(n + 1);
ABC[cur - 'A']++;
}
void dp(int n) {
if (n == input.size()) {
gotAns = true;
return;
}
else if (gotAns || (n > 1 && save[result[n - 2]-'A'][result[n - 1]-'A'][ABC[0]][ABC[1]][ABC[2]]))
return;
if (ABC[0] > 0)
goNext('A', n);
if (gotAns)
return;
if (ABC[1] > 0 && (n == 0 || result[n-1] != 'B'))
goNext('B', n);
if (gotAns)
return;
if(ABC[2] > 0 && (n == 0 || result[n - 1] != 'C') && (n <= 1 || result[n - 2] != 'C'))
goNext('C', n);
if (gotAns)
return;
if (n > 1) {
save[result[n - 2]-'A'][result[n - 1]-'A'][ABC[0]][ABC[1]][ABC[2]] = 1;
}
}