백준 2661 좋은수열

숫자 1, 2, 3으로만 이루어지는 수열이 있다. 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 그 수열을 나쁜 수열이라고 부른다. 그렇지 않은 수열은 좋은 수열이다.

다음은 나쁜 수열의 예이다.

33
32121323
123123213
다음은 좋은 수열의 예이다.

2
32
32123
1232123
길이가 N인 좋은 수열들을 N자리의 정수로 보아 그중 가장 작은 수를 나타내는 수열을 구하는 프로그램을 작성하라. 예를 들면, 1213121과 2123212는 모두 좋은 수열이지만 그 중에서 작은 수를 나타내는 수열은 1213121이다.

1. 인접한 두 개의 부분수열이 있을 때는 재귀를 멈추는 것이 핵심
   1-1. 인접한 두 개의 부분 수열이 있는지 없는지는 수열이 추가될 때마다

   • 뒤에서 1개와 그 뒤의 1개를 비교해서 같은 수열인지
   • 뒤에서 2개와 그 뒤의 2개를 비교해서 같은 수열인지
   • 뒤에서 len / 2개와 그 뒤의 len / 2개를 비교해서 같은 수열인지

2. 3개의 너비를 가진 트리

3. 가장 작은 수를 나타내는 수열만 리턴하면 되기 때문에
   가장 먼저 나오는 수열이 나타면 프로세스 종료

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

public class Main {
    static int N;
    static String cArr[] = {"1", "2", "3"};

   
    public static void main(String[] args) throws IOException {
        // 1, 2, 3 으로만 이루어진
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
//        System.out.println(check("32121"));
        DFS("", 0);
    }

    static void DFS(String str ,  int depth) {
        if(depth == N) {
            System.out.println(str);
            System.exit(0);
            return;
        }
        // 1. 앞의 글자와 같으면 들어갈 수 없다

        for(int i = 0; i < 3; i++) {

            if(check(str.concat(cArr[i]))) {
                DFS(str.concat(cArr[i]), depth+1);
            }

        }
    }
    static boolean check(String st) {
        int len = st.length() / 2;

        for(int i = 1; i <= len; i++) {
            if(st.substring(st.length() - i).equals(st.substring(st.length() - 2*i, st.length() - i))) return false;
        }



        return true;
    }
}