[백준]#14238 출근 기록

문제

스타트링크에는 세명의 직원이 일을 하고 있다. 세 직원의 이름은 강호(A), 준규(B), 수빈(C) 이다.

이 회사의 직원은 특별한 룰을 가지고 있는데, 바로 하루에 한 명만 출근한다는 것이다. 3일간의 출근 기록이 "AAC"라는 것은 처음 이틀은 A가 출근했고, 셋째 날엔 C만 출근했다는 뜻이다.

A는 매일 매일 출근할 수 있다. B는 출근한 다음날은 반드시 쉬어야 한다. C는 출근한 다음날과 다다음날을 반드시 쉬어야 한다. 따라서, 모든 출근 기록이 올바른 것은 아니다. 예를 들어, B는 출근한 다음날 쉬어야 하기 때문에, "BB"는 절대로 나올 수 없는 출근 기록이다.

출근 기록 S가 주어졌을 때, S의 모든 순열 중에서 올바른 출근 기록인 것 아무거나 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 출근 기록 S가 주어진다. S의 길이는 50을 넘지 않는다.

출력

S의 모든 순열 중에서 올바른 출근 기록인 것을 하나만 출력한다. 만약, 올바른 출근 기록이 없는 경우에는 -1을 출력한다.

예제 입력 1

CAB

예제 출력 1

BCA

예제 입력 2

CBB

예제 출력 2

BCB

예제 입력 3

BB

예제 출력 3

-1

예제 입력 4

BBA

예제 출력 4

BAB

풀이

이 문제는 dp(다이나믹 프로그래밍) 알고리즘을 이용해서 풀 수 있었다. DP 알고리즘을 이용한 문제 풀이는 항상 쉽게 생각하지 못하는 편이어서 좀 더 많은 문제를 풀어봐야 한다고 생각이 들었다.

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

public class Main {
    static int[][][][][] dp;
    static boolean flag = false;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new  BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();
        int a_cnt = 0;
        int b_cnt = 0;
        int c_cnt = 0;

        for(int i=0; i<input.length(); i++) {
            if(input.charAt(i)=='A')
                a_cnt++;

            else if(input.charAt(i)=='B')
                b_cnt++;

            else
                c_cnt++;
        }
        dp = new int[a_cnt+1][b_cnt+1][c_cnt+1][3][3];

        dfs(a_cnt, b_cnt, c_cnt, "", 0, 0);

        if(!flag)
            System.out.println(-1);
    }

    public static void dfs(int a, int b, int c, String s, int pre2, int pre) {
        if(flag) return;

        if(a==0 && b==0 && c==0) {
            System.out.println(s);
            flag = true;
            return;
        }

        if(dp[a][b][c][pre2][pre]==1) return;

        dp[a][b][c][pre2][pre] = 1;

        if(a>0)
            dfs(a-1, b, c, s+'A', pre, 0);

        if(b>0 && pre!=1)
            dfs(a, b-1, c, s+'B', pre, 1);

        if(c>0 && pre!=2 && pre2!=2)
            dfs(a, b, c-1,s+'C', pre, 2);
    }
}