Q 2661 좋은수열

💡 문제 요약 및 분석

1,2,3 으로만 이루어져 있는 길이가 N인 수열을 만들자. 단, 해당 수열에서 인접한 부분 수열이 동일한 것이 있으면 나쁜 수열이다. (예: 33, 32121323 등) 그렇지 않은 수열은 좋은 수열이다. 좋은 수열들 중에서 가장 작은 수를 나타내는 수열을 출력하자.

💡 알고리즘 설계

1. 입력

   • 표준입력 : int n

2. 연산

   • 숫자를 더할 때는 좋은 수열이 되는지 나쁜 수열이 되는지를 판별한 후, 좋은 수열이라면 더한다.
   • 전체 문자열의 절반 길이만큼 비교한다.
   • 새로운 숫자를 N번째로 가정하고, N과 N-1 을 비교 (한 자리 비교), N ~ N-1 과 N-2 ~ N-3 비교 (두 자리 비교), N ~ N-3 과 N-4 ~ N-6 비교 (세 자리 비교) 등등 진행하여 하나라도 일치하면 false 를 리턴한다.
   • count == n 일 때 프로그램을 완전히 종료한다.

3. 출력

   • 제일 첫 답을 출력한다.

💡 코드

public class Main {

    static int n;

    static int read() throws Exception {
        int c = 0, n = 0;
        while ((c = System.in.read()) > 47) n = (n << 3) + (n << 1) + (c & 15);
        return n;
    }

    public static void main(String[] args) throws Exception {
        n = read();
        backTracking(0, "");
    }

    static void backTracking(int count, String origin) {
        if (count == n) {
            System.out.println(origin);
            System.exit(0);
        }
        for (int i = 1; i <= 3; i++) {
            if (check(origin + i)) {
                backTracking(count + 1, origin + i);
            }
        }
    }

    static boolean check(String checkStr) {
        int len = checkStr.length() / 2;
        for (int i = 1; i <= len; i++) {
            if (checkStr.substring(checkStr.length() - i)
                    .equals(checkStr.substring(checkStr.length() - 2 * i, checkStr.length() - i))) {
                return false;
            }
        }
        return true;
    }

}

💡 시간 복잡도, 공간 복잡도

시간 복잡도	공간 복잡도
O(3^n * n)	O(n^2)