[알고리즘] 백준2661번 좋은수열 자바

백준 2661번: 좋은수열 문제 보러가기

 

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

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());
        backtracking("");
    }

    public static void backtracking(String str){

        for(int i=1;i<=3;i++){
            if(isGoodSeq(str)){
                if(str.length()==N){
                    System.out.println(str);
                    System.exit(0);
                }
                backtracking(str+i);
            }
        }
    }

    public static boolean isGoodSeq(String str){
        int level=str.length()/2;
        for(int i=1;i<=level;i++){
            if(str.isEmpty()) return true;
            String front_str = str.substring(str.length()-i-i, str.length()-i);
            String behind_str = str.substring(str.length()-i);
            if(front_str.equals(behind_str)) return false;

        }
        return true;
    }

}

문제 풀이 : 백트레킹을 이용하여 푸는데 isGoodSeq에서 이전에 확인되었던거는 하지 않고 str의 뒤쪽이 좋은수열인지 아닌지만 판단하면 된다.