[백준] 14238 출근기록

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class B14238 {
	static boolean[][][][][] dp;
	static int[] abc = new int[3];
	static boolean flag;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		char arr[] = br.readLine().toCharArray();
		
		for (int i = 0; i < arr.length; i++) {
			if(arr[i]=='A') abc[0]++;
			else if(arr[i]=='B') abc[1]++;
			else abc[2]++;
		}
		
		dp = new boolean[abc[0]+1][abc[1]+1][abc[2]+1][3][3];
		search(abc[0],abc[1],abc[2],0,0, new String(""));
		
		if(!flag) System.out.println(-1);
	}
	
	private static void search(int a, int b, int c, int i, int j, String str) {
		if(flag) return;
		
		if(a==0&&b==0&&c==0) {
			System.out.println(str);
			flag = true;
			return;
		}
		
		if(dp[a][b][c][i][j]) return;
		dp[a][b][c][i][j] = true;
		
		// c가 있고 이전값과 그전값 확인
		if(c>0&&i!=2 &&j!=2 ) search(a,b,c-1,j,2,str+"C");
		// b가 있고 이전값 확인
		if(b>0&&j!=1 ) search(a,b-1,c,j,1,str + "B");
		// a가 있을 때
		if(a>0) search(a-1,b,c,j,0,str + "A");
		
		
	}

}