[백준] 14238 출근기록

문제보기

import java.util.*;
import java.io.*;

public class Main{
  // A,B,C 갯수가 1행 2행 3행에 들어가고 4행은 이전 글자, 5행은 그 이전 글자를 나타낸다
	// 글자수 맥스가 50개라서 51개로 그냥 초기화
  static int[][][][][] d = new int[51][51][51][3][3];
  
  // DP - Top Down
  static int go(int a, int b, int c, int p1, int p2){
		
    // 주어진 a,b,c를 모두 다 소진했다면 - 이건 가능한 경우임
    if(a+b+c == 0){
      // 메모이제이션
      d[a][b][c][p1][p2] = 1;
      // 리턴값을 넘겨야 이전에 이 go를 호출했던 녀석도 1을 가져갈 수 있는것이다
      return 1;
    }
    
    // 이미 구했던 적이 있는 값이라면 그냥 출력하자
    if(d[a][b][c][p1][p2] != -1){
      return d[a][b][c][p1][p2];
    }

    // 아직 쓸 수 있는 a가 남아있으면 & 그 a를 썼을 때의 결과가 참이면(1)
    if( a > 0 && go(a-1, b, c, 0, p1) == 1 ){
      // 지금 이녀셕도 참인 셈이다. 메모이제이션
      d[a][b][c][p1][p2] = 1;
      // 지금 이 go를 호출한 이전 go도 1을 가져가야 한다
      return 1;
    }
    
    // 아래도 같은 원리. 단 b와 c는 p1,p2조건이 걸리므로 주의
    if( b > 0 && p1 != 1 && go(a, b-1, c, 1, p1) == 1){
      d[a][b][c][p1][p2] = 1;
      return 1;
    }
    if( c > 0 && p1 != 2 && p2 != 2 && go(a, b, c-1, 2, p1) == 1){
      d[a][b][c][p1][p2] = 1;
      return 1;
    }
		
    // 앞선 if에 하나도 걸리지 못했다면 이건 불가능한 경우다.
    // 메모이제이션 해주자
    d[a][b][c][p1][p2] = 0;
    // 날 부른 go.. 미안해.. 난 안돼..
    return 0;
  }

  // 출력을 위한 함수
  static String back(int a, int b, int c, int p1, int p2){
    // abc를 모두 소진했다면 빈 문자열을 출력하자 - 종료
    if(a+b+c == 0){
      return "";
    }
    
    // 아직 사용 가능한 a가 있고 & a를 사용한 결과가 가능한 경우라면
    if(a>0 && go(a-1,b,c,0,p1) == 1){
      // A를 출력하자
      return "A" + back(a-1,b,c,0,p1);
    }
    // 아래도 다 마찬가지 원리 
    if(b>0 && p1 != 1 && go(a,b-1,c,1,p1)==1){
      return "B" + back(a,b-1,c,1,p1);
    }
    if(c>0 && p1 != 2 && p2 != 2 && go(a,b,c-1,2,p1)==1){
      return "C" + back(a,b,c-1,2,p1);
    }
    
    // 이건 형식적인거고
    return "";
  }

  public static void main(String []args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String s = br.readLine();
    int[] abc = new int[3];
    // a,b,c 갯수를 각각 입력받자
    for(int i = 0 ; i < s.length() ; i++ ){
      abc[s.charAt(i)-'A']++;
    }
		
    // d는 -1로 초기화 - 아직 구한 적 없는 값이란 뜻 
    for(int i = 0 ; i <= 50 ; i++ ){
      for(int j = 0 ; j <=50 ; j++ ){
        for(int k = 0 ; k <= 50 ; k++ ){
          for(int l = 0 ; l < 3 ; l++ ){
            Arrays.fill(d[i][j][k][l], -1);
          }
        }
      }
    }
    
    //p1,p2에 0을 넣는 이유는 A는 무해한 녀석이기 때문이다
    int ans = go(abc[0], abc[1], abc[2], 0, 0);
    
    if( ans == 0 ){
      System.out.println(-1);
    }else{
      System.out.println(back(abc[0], abc[1], abc[2], 0, 0 ));
    }

  }
}