์•Œ๊ณ ๋ฆฌ์ฆ˜

  1. DP ์‚ฌ์šฉ
  2. ์•ž์—์„œ๋ถ€ํ„ฐ ๋ฐฑํŠธ๋ž˜ํ‚น์ฒ˜๋Ÿผ ์กฐ๊ฑด์ด ๋งž์„๋•Œ ์ „์ง„
  3. ๋งŒ์•ฝ ๋๊นŒ์ง€ ๊ฐ”์œผ๋ฉด gotAns = true ์„ค์ •ํ•˜์—ฌ, true์ด๋ฉด ๋ฐ”๋กœ ์ข…๋ฃŒ.
  4. ๋งŒ์•ฝ ๋๊นŒ์ง€ ์•ˆ๊ฐ”์œผ๋ฉด, save์— ์ €์žฅ
  5. ์ด๋•Œ save[ํ˜„์žฌ-2 ๋ฌธ์ž][ํ˜„์žฌ-1๋ฌธ์ž][๋‚จ์€ A][๋‚จ์€ B][๋‚จ์€ C] ๋กœ ํ•จ
    1. ํ˜„์žฌ ์ƒํƒœ๋ฅผ ๊ฒฐ์ •ํ•˜๋Š” ๊ฑด, ์ „์ „๋ฌธ์ž, ์ „ ๋ฌธ์ž, ๋‚จ์€ A์˜ ๊ฐœ์ˆ˜, ๋‚จ์€ B์˜ ๊ฐœ์ˆ˜, ๋‚จ์€ C์˜ ๊ฐœ์ˆ˜๋กœ ๊ฒฐ์ •๋˜๋ฏ€๋กœ.
    2. ์‚ฌ์šฉํ•œ A,B,C ์˜ ๊ฐœ์ˆ˜๊ฐ€ ๊ฐ™๋‹ค๋ฉด, ํ˜„์žฌ-2 ์ด์ „์˜ ๋ฌธ์ž ๋ฐฐ์—ด์€ ์ƒ๊ด€์—†๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค.
  6. 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;
	}
}