[백준 2661] 좋은수열

 

최소값을 구해야 하므로 조건을 만족하는 수 중 가장 작은것을 우선 출력하게 해야한다.

그리디하게 생각해보면 첫번째 수는 무조건 1이 된다.

 

수를 이어붙일 때마다 좋은 수열인지 여부를 체크해준다.

 

11 : 수의 길이가 2이면 1번만 검사하면 된다.

1212 : 수의 길이가 4이면 밑줄친 1과 2 검사 1번 + 12, 12 검사 1번, 총 2번해야 한다.

123123 : 수의 길이가 6이면 2,3 / 31, 23 / 123, 123 총 3번해야 한다.

 

따라서 검사 횟수는 수의 길이/2이다.

검사할 인덱스 지정은 의식의 흐름대로 하여서 로직을 보는 편이 좋을 듯 하다.

 

 

public class Main {
    
    static int n;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        n = Integer.parseInt(br.readLine());
        
        dfs(1, "1");
    }
    
    public static void dfs(int idx, String s) {
        if(n == idx) {
            System.out.println(s);
            System.exit(0);
        }
        
        for(int i=1; i<=3; i++)
            if(goodSeq(s + i))
                dfs(idx+1, s+i);
    }
    
    public static boolean goodSeq(String str) {
        int s = str.length()-1;
        int e = str.length();
        
        for(int i=1; i<=str.length()/2; i++) {
            if(str.substring(s-i, e-i).equals(str.substring(s, e)))
                return false;
            s--;
        }
        return true;
    }
}