[C++]백준 14238 - 출근 기록

14238번: 출근 기록

코드

---

#include <iostream>
#include <queue>
#include <string>
#include <vector>
#include <math.h>
using namespace std;
int workerCount[3];
bool dp[51][51][51][3][3] = { false };
char ans[51];
bool DP(int a, int b, int c, int bbefore, int before) {
	if (workerCount[0] == a && workerCount[1] == b && workerCount[2] == c) {
		return true;
	}
	if (dp[a][b][c][bbefore][before])
		return false;
	dp[a][b][c][bbefore][before] = true;

	if (a + 1 <= workerCount[0]) {
		ans[a + b + c] = 'A';
		if (DP(a + 1, b, c, before, 0))
			return true;

	}
	if (b + 1 <= workerCount[1]) {
		ans[a + b + c] = 'B';
		if (before != 1) {
			if (DP(a, b + 1, c, before, 1))
				return true;
		}
	}
	if (c + 1 <= workerCount[2]) {
		ans[a + b + c] = 'C';
		if (bbefore != 2 && before != 2) {
			if (DP(a, b, c + 1, before, 2))
				return true;
		}
	}
	return false;
}
int main() {
	string companyLog;
	cin >> companyLog;
	for (int i = 0; i < companyLog.size(); i++) {
		if (companyLog[i] == 'A')
			workerCount[0]++;
		if (companyLog[i] == 'B')
			workerCount[1]++;
		if (companyLog[i] == 'C')
			workerCount[2]++;
	}
	if (DP(0, 0, 0, -1, -1)) {
		for (int i = 0; i < companyLog.size(); i++) {
			cout << ans[i];
		}
	}
	else {
		cout << -1; 
	}
	return 0;
}