백준 1343번 폴리오미노 (JAVA)

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

1343번: 폴리오미노

 

저는 DP를 이용하였습니다.

해당 depth부터 연속적으로 .이 몇개 있는지를 판단하여 AAAA 또는 BB를 넣을지를 판단하여 dfs를 통해 모든 경우를 찾았습니다. 이때 중복되는 경우는 다시 계산하지 안도록 하기위해 DP를 이용하였습니다.

 

package BOJ.dp;

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

public class BOJ_1343 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String command = br.readLine();
        String result = cal(0,command);
        System.out.println(result);
    }
    private static final String NOT_FOUND = "-1";
    private static String cal(int depth, String command) {
        if(depth == command.length()){
            return "";
        }
        if(command.charAt(depth) == '.'){
            String temp = cal(depth+1,command);
            if(temp.equals(NOT_FOUND)){
                return NOT_FOUND;
            }
            return '.'+temp;
        }
        boolean[] can = new boolean[4];
        boolean flag = true;
        for(int i = 0 ; i < 4 && depth + i < command.length(); i++){
            if(command.charAt(depth+i) == '.'){
                flag = false;
            }
            can[i] = flag;
        }
        String result = NOT_FOUND;
        if(can[1]){
            String temp = cal(depth+2,command);
            if(!temp.equals(NOT_FOUND)){
                result = "BB" + temp;
            }
        }
        if(can[3]){
            String temp = cal(depth+4,command);
            if(!temp.equals(NOT_FOUND)){
                result = "AAAA" + temp;
            }
        }
        return result;
    }

}