[백준] 2661 좋은수열

 

 

 

---

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

public class Main {
	static int N;
	static int[] arr;
	static String result = "";
	public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	N = Integer.parseInt(br.readLine());
	dfs(0);
	//System.out.println(result);
	}
	static void dfs(int count) {
		int div = (count + 1) / 2;
		if(count == N) {
			System.out.println(result);
			System.exit(0);
		}
		for(int i = 1; i <= 3; i++) {
			if(good_Sequence(i,  div , count)) {
				result += i;
				dfs(count+1);
				result = result.substring(0,count);
			}
		}
	}
	static boolean good_Sequence(int a ,int divide, int count) {
		String temp = result;
		temp += a;
		if(divide == 0) {
			return true;
		}
		if(temp.charAt(count-1) == temp.charAt(count)) {
			return false;
		}
		if(divide >= 2) {
			for(int i = 2; i <= divide; i++) { //12일때 di는 1
				if(temp.substring(count-i-(i-1),count-i+1).equals(temp.substring(count-i+1,count+1))) {
					return false;
				}
			}
		}
		return true;
	}
}