[백준 2661] 좋은수열 (JAVA)

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

2661번: 좋은수열

 

백트래킹을 사용하여 해결하면 된다.

연속되는 숫자중에 같은 부분이 있는지 확인하며 수열을 만들어나간다.

제일 작은 수열이므로 가장 먼저 만들어질 것이기에 수열의 길이가 n일 경우 프로그램을 종료시킨다.

 

 

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

public class Main {
	static int n;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		 n= Integer.parseInt(br.readLine());
		back("1");

	}
	static void back(String str) {
		if(str.length()==n) {
			System.out.println(str);
			System.exit(0);
		}
		for(int i=1;i<=3;i++) {
			if(find(str+i)) {
				back(str+i);
			}
		}
	}
	static boolean find(String str) {
		for(int j=1;j<=str.length()/2;j++) {
			for(int k=0;k<=str.length()-2*j;k++) {
				if(str.substring(k, k+j).equals(str.substring(k+j,k+j+j))) {
					return false;
				}
			}
		}
		return true;
	}

}