[백준 14238] 출근 기록 (C++)

문제 링크: https://www.acmicpc.net/problem/14238

14238번: 출근 기록

1. 주의할 점

- DFS로 시도할 경우, 3^50의 경우이며 몇 가지 추가조건을 건다고 해도 결과는 TLE

- 메모라이즈를 사용한다. 마지막으로 사용했던 2개만 기억하면 된다고 생각한다.

- 입력받은 문자열에 몇개의 A,B,C가 있는지 따로 기록해야 한다.

 

2. 구현

- 메모라이즈를 통해 Bool 형태의 배열을 만들어놓고 가능하면 True를 아니면 False를 반환한다

- DP[사용한 A의 개수][사용한 B의 개수][사용한 C의 개수][마지막에서 2번째로 사용한 문자][마지막으로 사용한 문자] 형태의 배열을 사용한다

 

[TLE - 시간초과]

#include <iostream>
#include <string>
using namespace std;
int have_alpha[3];	//입력받은 alphabet 개수 체크
string s;
bool finish = false;

void start(int cnt, int a, int b, int c, string ans) {
	if (finish) return;
	if (cnt == s.size()) {
		cout << ans;
		finish = true;
		return;
	}
	int na = a, nb = b, nc = c;
	if (na > 0) na -= 1;
	if (nb > 0) nb -= 1;
	if (nc > 0) nc -= 1;

	if (have_alpha[0] > 0) {		//a 사용 가능
		have_alpha[0]--;
		start(cnt + 1, na, nb, nc, ans + 'A');
		have_alpha[0]++;
	}
	if (have_alpha[1] > 0 && nb==0) {		//b 사용 가능
		have_alpha[1]--;
		start(cnt + 1, na, 2, nc, ans + 'B');
		have_alpha[1]++;
	}
	if (have_alpha[2] > 0 && nc == 0) {		//c 사용 가능
		have_alpha[2]--;
		start(cnt + 1, na, nb, 3, ans + 'C');
		have_alpha[2]++;
	}
}

int main() {
	cin >> s;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == 'A') have_alpha[0]++;
		else if (s[i] == 'B') have_alpha[1]++;
		else have_alpha[2]++;
	}
	start(0, 0, 0, 0, "");
	if (!finish) cout << -1;
	return 0;
}

 

 

[성공]

#include <iostream>
#include <string>
using namespace std;
int have_alpha[3];	//입력받은 alphabet 개수 체크
string s;
bool dp[51][51][51][3][3] = { false, };
char ans[51];
bool start(int a, int b, int c, int back1,int back2) {
	if (a==have_alpha[0] && b == have_alpha[1] && c == have_alpha[2]) {
		return true;
	}
	if (dp[a][b][c][back1][back2]) return false;
	dp[a][b][c][back1][back2] = true;

	if (a+1<=have_alpha[0]) {		//a 사용 가능
		ans[a + b + c] = 'A';
		if (start(a + 1, b, c, back2, 0))
			return true;

	}
	if (b + 1 <= have_alpha[1]) {
		ans[a + b + c] = 'B';
		if (back2 != 1) {		//b 사용 가능
			if (start(a, b + 1, c, back2, 1))
				return true;
		}
	}
	if (c + 1 <= have_alpha[2]) {
		ans[a + b + c] = 'C';
		if (back1 != 2 && back2 != 2) {		//c 사용 가능
			if (start(a, b, c + 1, back2, 2))
				return true;
		}
	}
	return false;
}

int main() {
	cin >> s;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == 'A') have_alpha[0]++;
		else if (s[i] == 'B') have_alpha[1]++;
		else have_alpha[2]++;
	}
	if (start(0, 0, 0, -1, -1))
		for (int i = 0; i < s.size(); i++)
			cout << ans[i];
	else	cout << -1;
	system("pause");
	return 0;
}