[boj] 좋은수열_2661 JAVA

문제는 이러하다.

 

먼저, 수열은 1, 2, 3만 사용하므로 배열 list에 이를 저장한다.

답은 무조건 9보다 작기 때문에 answer을 9 로 설정해놓는다!

 

DFS를 돌면서, 현재 수열에서 마지막 두 개의 인접한 부분 수열을 비교하고

 

만약 인접한 부분 수열이 동일하면 해당 수열은 나쁜 수열로 간주,

그렇지 않으면 탐색을 계속 진행하여 수열을 확장하기!

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.*;
import java.util.*;
 
 
public class Main {
 
    static int n;
    static String[] list = {"1", "2", "3"};
    static String answer = "9";
 
    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(answer);
    }
 
    private static void dfs(int index, String origin) {
        if (index == n) {
            System.out.println(origin);
            System.exit(0);
        }
 
        for (int i = 0; i <= 2; i++) {
            if (check(origin+list[i])) {
                dfs(index + 1, origin + list[i]);
            }
        }
    }
 
    private static boolean check(String checkStr) {
        int length = checkStr.length() / 2;
 
        for (int i = 1; i <= length; i++) {
            if (checkStr.substring(checkStr.length() - i).equals(checkStr.substring(checkStr.length() - 2 * i, checkStr.length() - i))) {
                return false;
            }
        }
 
        return true;
    }
}