[BOJ 14238] 출근 기록 (Java)

BOJ 14238 출근 기록

난이도 : 골드 3

https://www.acmicpc.net/problem/14238

14238번: 출근 기록

 

전략

S의 길이가 최대 50이므로, 모든 경우의 수를 다 탐색하면 안된다.

 

메모이제이션을 사용해서 중복된 연산을 제거해야 한다.

 

불가능한 것이 계산된 (방문된) 상태는 bool 타입의 dp 배열을 통해 검사하여 제거할 수 있다.

 

경우의 수 탐색은 재귀 호출로 구현된 dfs로 이루어진다.

 

시행착오

처음에는 dp의 기준을 dp[현재 idx][남은 a][남은 b][남은 c] 로 하고, 배열 seq의 상태를 통해 b, c를 놓을 수 있는지 확인했는데

 

이렇게 하면 배열의 상태가 계속 변하기 때문에 dp의 의미가 없어진다.

 

필요한 모든 정보를 dp에 담기 위해서는 b, c에 영향을 미치는 마지막에서 2개의 출근 기록을 고려해야한다.

 

코드

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

public class Main {

    static char[] seq;
    static boolean[][][][][] dp;
    static int S;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        S = str.length();
        int[] freq = new int[3];
        seq = new char[S + 1];
        dp = new boolean[S + 1][S + 1][S + 1][3][3];

        for (int i = 0; i < str.length(); i++)
            freq[str.charAt(i) - 'A']++;

        if (solution(freq[0], freq[1], freq[2], 0, 0))
            System.out.println(seq);
        else
            System.out.println(-1);
    }

    static boolean solution(int a, int b, int c, int yd2, int yd1) {
        if (a == 0 && b == 0 && c == 0) return true;

        if (dp[a][b][c][yd2][yd1]) return false;
        dp[a][b][c][yd2][yd1] = true;

        if (a > 0) {
            seq[S - a - b - c] = 'A';
            if (solution( a - 1, b, c, yd1, A)) return true;
        }
        if (b > 0 && yd1 != B) {
            seq[S - a - b - c] = 'B';
            if (solution(a, b - 1, c, yd1, B)) return true;
        }
        if (c > 0 && yd2 != C && yd1 != C) {
            seq[S - a - b - c] = 'C';
            if (solution(a, b, c - 1, yd1, C)) return true;
        }

        return false;
    }

    static final int A = 0;
    static final int B = 1;
    static final int C = 2;

}

 

깨달은 점

dp를 구성할 때 탐색에 영향을 미치는 변수들을 반드시 메모이제이션에 포함시켜야 한다고 깨달았다.