백준 2661 좋은수열 자바(java)

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

2661번: 좋은수열

 

풀이 방법

dfs + 백트래킹 알고리즘을 사용한다.

1, 2, 3 을 차례대로 문자열에 붙여주면서 만들어지는 문자열이 나쁜 수열인지 체크하고 나쁜 수열인 경우엔 탐색을 멈추고 백트래킹한다. 나쁜 수열인지 확인하는 방법은 현재 문자열 길이를 2로 나누어 최대 부분수열의 크기를 구하고, 부분수열의 크기를 2부터 최대 크기까지 늘려가면서 연속되는 두 부분수열의 문자열이 같은지 확인해주면 된다.

부분수열의 크기를 2부터 보는 이유는 dfs 함수를 재귀 호출 시 이전 숫자와 같은 숫자는 제외하도록 이미 조건을 주었기 때문이다. 이렇게 탐색하여 만들어지는 첫번째 N자리 수열이 정답이 된다.

오름차순으로 숫자를 탐색하므로 처음으로 만들어지는 N자리 수열은 가장 작은 수라는 조건이 보장된다.

 

코드

import java.util.Scanner;

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

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        dfs("", 0); // dfs 탐색
        System.out.println(answer);
    }

    // dfs 탐색
    public static void dfs(String str, int len) {

        if(!answer.isEmpty()) {
            return;
        }
        // 나쁜 수열인지 확인하고, 나쁜 수열이면 탐색을 멈춤(가지치기 조건)
        if(len > 3 && !check(str)) {
            return;
        }

        // N 자리 좋은 수열을 만든 경우
        if(len == N) {
            answer = str;
            return;
        }

        for(int i=0; i<3; i++) {
            // 앞의 숫자와 같지 않은 숫자만 붙임
            if(len == 0 || (len > 0 && str.charAt(len-1) != numbers[i].charAt(0))) {
                dfs(str + numbers[i], len+1);
            }
        }
    }

    // 나쁜 수열인지 체크
    public static boolean check(String str) {
        int len = str.length(); // 현재 문자열 길이
        int size = (int)len / 2; // 부분수열의 최대 길이
        for(int l=2; l<=size; l++) { // 가능한 부분수열의 크기마다 유효한지 체크
            // 두 개의 연속된 부분수열이 같으면
            if(str.substring(len-l, len).equals(str.substring(len-2*l, len-l))) {
                return false;
            }
        }
        return true;
    }
}