[JAVA] 백준 12659 - Welcome to Code Jam (Small)

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

 주어지는 문자열에서 문자열을 순서대로 읽으면서 "welcome to code jam"이라는 문장을 몇 번 만들 수 있는지 구하는 문제이다.

 

시간 제한이 5초이고 문자열의 길이가 최대 30이어서 dfs로 가능한 모든 조합을 구한 뒤 "welcome to code jam"이 완성되는 경우 카운트를 증가시켰다.

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

public class Main {
    static int count = 0;
    static String target = "welcome to code jam";
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = par(br.readLine());
        for (int i = 0; i < tc; i++) {
            String s = br.readLine();
            count = 0;
            for (int j = 0; j < s.length(); j++) {
                dfs(s,j,new StringBuilder());
            }
            System.out.println("Case #"+(i+1)+": " + lpad(count));
        }
    }
    static String lpad(int t){
        String s = String.valueOf(t);
        if(s.length()>4){
            s = s.substring(s.length()-4);
        }else{
            while(s.length()!=4){
                s = "0".concat(s);
            }
        }
        return s;
    }
    static void dfs(String s, int i, StringBuilder sb){
        char c = s.charAt(i);
        sb.append(c);
        if(!target.startsWith(sb.toString())) return;
        if(sb.toString().equals(target)){
            count++;
            return;
        }
        for (int j = i+1; j < s.length(); j++) {
            dfs(s,j,new StringBuilder(sb));
        }
    }

    static int par(String s) {
        return Integer.parseInt(s);
    }
}