[백준] 2661번 좋은 수열 (gold 4

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

public class Main{
    static boolean get=false;
    static String answer="";
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        int t=Integer.valueOf(br.readLine());
        dfs("1",t);
        bw.write(answer);
        bw.flush();

    }
    //백트래킹으로 풀이.
    public static void dfs(String str, int max ){
        //답을 구한 경우 return
        if(get){
            return;
        }
        //불가상태 혹은, 길이가 max이면 return. (더이상 할 필요x
        boolean can=possible(str);
        if(!can || (!can && str.length()==max)){
            return;
        }
        //만약 가능상태에 길이가 원하는 길이면 해당케이스 정답.
        //답 찾았다고 수정. 답 저장
        else if(can && str.length()==max){
            answer=str;
            get=true;
        }
        //dfs순서를 1,2,3으로 조정. 이렇게 할 경우 작은 수를 우선으로 dfs진행하므로
        //결과는 원하는 가장 작은 수가 됨
        dfs(str.concat("1"),max);
        dfs(str.concat("2"),max);
        dfs(str.concat("3"),max);
    }
    public static boolean possible(String str){
        //str가능한 상태인지 확인 아니면 return
        //브루트포스로 해당 겹치는 영역 길이마다 확인
        boolean can=true;
        int div=str.length()/2;
        for(int i=1; i<=div; i++){
            if(str.substring(str.length()-i,str.length())
                    .equals(str.substring(str.length()-2*i, str.length()-i))){
                can=false;
                break;
            }
        }
        return can;
    }
}