Algorithm, boj, 출근기록(14238)

출근기록

비슷한 문제 - ABC

다른분 풀이

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

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

#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;
}

나의 코드

• 현재자리에는 a,b,c 세개가 규칙에 위배되지 않을경우 각각 올수있다.
• dp[x][c][b][a] : x까지의 a,b,c를 사용해서 만들수있는지 확인한다.

내 풀이의 개선점

• DP[사용한 A의 개수][사용한 B의 개수][사용한 C의 개수][마지막에서 2번째로 사용한 문자][마지막으로 사용한 문자] 내풀이 보다는 이걸로 바꾸는게 좋을것같다.
• 내 풀이의 x는 a+b+c 개수를 각각 더하면 쉽게 알수있고, 중요한 정보가 아니다.
• 여기서 중요한건 마지막으로 사용, 마지막 전에 사용한 문자가 중요하다.

package org.baekjoon;

import java.util.Scanner;

public class test14238 {
	static int length;
	static boolean[][][][] dp;
	static char S[];
	static final int NOT_EXIST = -1;
	static int A = 0, B = 0, C = 0;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String str = sc.next();
		length = str.length();
		// dp[x][c][b][a] : x까지의 a,b,c를 사용해서 만들수있는지 확인한다.
		dp = new boolean[length][length][length][length];
		S = new char[length];

		for (int i = 0; i < length; i++) {
			switch (str.charAt(i)) {
			case 'A':
				A++;
				break;
			case 'B':
				B++;
				break;
			case 'C':
				C++;
				break;

			}
		}

		if (solve(0, 0, 0, 0)) {
			System.out.println(new String(S));
		} else {
			System.out.println(NOT_EXIST);
		}
	}

	private static boolean solve(int x, int c, int b, int a) {
		//System.out.println("x=" + x + " c=" + c + " b=" + b + " a=" + a + " string=" + new String(S));

		if (x == length) {
			return true;
		}

		// x자리 까지 a,b,c 를 사용해서 가능한지 확인했었기 때문에 또 확인 하지 않는다.
		if (dp[x][c][b][a] == true)
			return false;

		// x위치에서 A를 a개 B를 b개 C를c개 사용해서 문자열 만들수있는지 확인할것이므로 true
		dp[x][c][b][a] = true;

		// X위치에 C,B,A가 들어갈수있는지 확인한다.
		// 남아있는 C개수가있는지 확인 후 사용.
		if (C > c) {
			// 이전, 이이전에 사용했는지 확인후 아니라면 시도해본다.
			if ((x >= 2 && (S[x - 1] != 'C' && S[x - 2] != 'C')) ||
					(x == 1 && S[x - 1] != 'C') || x == 0) {
				S[x] = 'C';
				if (solve(x + 1, c + 1, b, a))
					return true;
			}
			else	// 규칙에 의해 검사 못했으므로  다시 false해준다.
				dp[x][c][b][a] = false;

		}

		// 남아있는 B개수가있는지 확인 후 사용.
		if (B > b) {
			// 이전에 사용했는지 확인하고 아니라면 시도한다.
			if ((x >= 1 && S[x - 1] != 'B') || x == 0) {
				S[x] = 'B';
				if (solve(x + 1, c, b + 1, a))
					return true;
			}else
				dp[x][c][b][a] = false;
		}

		// 남아있는 A개수가있는지 확인 후 사용.
		if (A > a) {
			// 아무때나 시도 가능.
			S[x] = 'A';
			if (solve(x + 1, c, b, a + 1))
				return true;
		}

		return false;
	}

}