์๊ณ ๋ฆฌ์ฆ
- DP ์ฌ์ฉ
- ์์์๋ถํฐ ๋ฐฑํธ๋ํน์ฒ๋ผ ์กฐ๊ฑด์ด ๋ง์๋ ์ ์ง
- ๋ง์ฝ ๋๊น์ง ๊ฐ์ผ๋ฉด gotAns = true ์ค์ ํ์ฌ, true์ด๋ฉด ๋ฐ๋ก ์ข
๋ฃ.
- ๋ง์ฝ ๋๊น์ง ์๊ฐ์ผ๋ฉด, save์ ์ ์ฅ
- ์ด๋ save[ํ์ฌ-2 ๋ฌธ์][ํ์ฌ-1๋ฌธ์][๋จ์ A][๋จ์ B][๋จ์ C] ๋ก ํจ
- ํ์ฌ ์ํ๋ฅผ ๊ฒฐ์ ํ๋ ๊ฑด, ์ ์ ๋ฌธ์, ์ ๋ฌธ์, ๋จ์ A์ ๊ฐ์, ๋จ์ B์ ๊ฐ์, ๋จ์ C์ ๊ฐ์๋ก ๊ฒฐ์ ๋๋ฏ๋ก.
- ์ฌ์ฉํ A,B,C ์ ๊ฐ์๊ฐ ๊ฐ๋ค๋ฉด, ํ์ฌ-2 ์ด์ ์ ๋ฌธ์ ๋ฐฐ์ด์ ์๊ด์๊ธฐ ๋๋ฌธ์ด๋ค.
- DP ํจ์ ์์๋ถ๋ถ์ ํ์ฌ ์ํ์ save๊ฐ true์ด๋ฉด ํ์ฌ dp ์ข
๋ฃ
์ฝ๋
#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;
}
}