BOJ - 좋은 수열

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

2661번: 좋은수열

 

• 주어진 좋은 수열을 만족하는 경우에만 123 탐색을 진행했다.
• 123 중복을 허용하는 순으로 진행했기 때문에 가장 작은 수는 가장 첫 번째 발견되는 수열이다.

 

import java.io.*;

public class Main {

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static char[] words = new char[]{
            '1', '2', '3'
    };

    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(br.readLine());
        dp(0, "", N);
    }

    private static void dp(int depth, String combination, int length) {
        if (combination.length() == length) {
            if (isValid(combination)) {
                System.out.println(combination);
                System.exit(0);
            }
            return;
        }

        for (int i = 0; i < words.length; i++) {
            if (!isValid(combination)) continue;
            dp(depth + 1, combination + words[i], length);
        }
    }

    private static boolean isValid(String combination) {
        if (combination.length() == 1) return true;

        for (int length = 1; length <= combination.length() / 2; length++) {
            for (int i = 0; i <= combination.length() - length * 2; i++) {
                String front = combination.substring(i, i + length);
                String rear = combination.substring(i + length, i + length + length);
                if (front.equals(rear)) {
                    return false;
                }
            }
        }

        return true;
    }
}